15分球调
查看原帖
15分球调
1517945
Citlali楼主2024/11/9 15:47

AC:#1,#5,#17

#include<bits/stdc++.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
const int N=1e6+20;
struct node{
    double x,y;
}p[N],stk[N];
int n;
double check(node a1,node a2,node b1,node b2){
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double dist(node a,node b){
    return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
bool cmp(node p1,node p2){
    double tmp=check(p[1],p1,p[1],p2);
    if(tmp>0){
    	return 1;
	}
	if(tmp==0&&dist(p[1],p1)<dist(p[1],p2)){
	    return 1;
	}
    return 0;
}
void graham(){
    sort(p+2,p+n+1,cmp);
    stk[1]=p[1];
    int cnt=1;
    for(int i=2;i<=n;i++){
        while(cnt>1&&check(stk[cnt-1],stk[cnt],stk[cnt],p[i])<=0){
        	cnt--;
		}
        cnt++;
        stk[cnt]=p[i];
    }
    stk[cnt+1]=p[1];
    double ans=0;
    for(int i=1;i<=cnt;i++){
		ans+=dist(stk[i],stk[i+1]);
    }
    cout<<cnt+1;
}
double ds;       
void click(int k){
    ds=p[1].y;
    p[1].y=p[k].y;
    p[k].y=ds;
    ds=p[1].x;
    p[1].x=p[k].x;
    p[k].x=ds;
}
int main(){
	bool flagx=1,flagy=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
		if(i!=1&&(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x))){
            click(i);
        }
    }
    graham();
} 
2024/11/9 15:47
加载中...