本文共 1216 字，大约阅读时间需要 4 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std;17 typedef long long ll;18 typedef unsigned long long ull;19 20 struct P21 {22 int x,y;23 };24 25 26 const int maxn=50050;27 int n,k;28 P ps[maxn];29 30 bool cmp(const P& p,const P& q)31 {32 if(p.x!=q.x)33 return p.x convex_hull(P* ps,int n)43 {44 sort(ps,ps+n,cmp);45 k=0;46 vector qs(n*2);47 for(int i=0;i 1 && cross(qs[k-2],qs[k-1],ps[i])<=0)49 k--;50 qs[k++]=ps[i];51 }52 for(int i=n-2,t=k;i>=0;i--){53 while(k>t && cross(qs[k-2],qs[k-1],ps[i])<=0)54 k--;55 qs[k++]=ps[i];56 }57 k--;58 qs.resize(k);59 return qs;60 }61 62 double dis(P p,P q)63 {64 double dist=(p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);65 return sqrt(dist);66 }67 68 69 int main()70 {71 while(~scanf("%d",&n)){72 if(n==0)73 return 0;74 for(int i=0;i qs=convex_hull(ps,n);77 double ans=0;78 if(k==0||k==1)79 printf("0\n");80 else if(k==2)81 printf("%.2lf\n",dis(qs[0],qs[1]));82 else{83 for(int i=0;i
qs(n*2);47 for(int i=0;i
转载于:https://www.cnblogs.com/ooozy/p/6273776.html