7-15 长城 (凸包)

    科技2025-09-22  24

    #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+100; set<int> s; struct Point{ int x,y; }p[N]; Point ch[N]; bool cmp(Point x,Point y){ return x.x<y.x||(x.x==y.x&&x.y<y.y);//x从小到大排序,如果x相同则y从小到大排序 } int Cross(Point x,Point y,Point z){ ll x1=x.x-y.x; ll y1=x.y-y.y; ll x2=z.x-y.x; ll y2=z.y-y.y; if((x1*y2-x2*y1)<=0) return 0;//在右边(关于 2. ) return 1; } int main(){ int n;scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&p[i].x,&p[i].y); } //sort(p,p+n,cmp); int m=0; //从左到右扫描 for(int i=0;i<n;i++){ bool f=false; while(m>1&&!Cross(ch[m-1],ch[m-2],p[i])){ f=true; m--; } if(!f&&i>1) s.insert(ch[m-1].x); ch[m++]=p[i]; } cout<<s.size()<<endl; return 0; }

     

    Processed: 0.020, SQL: 8