当前位置：首页 > news >正文

POJ2187 旋转卡壳求最长直径

news 来源：原创 2024/5/6 11:03:51

给定平面上的一些散点集，求最远两点距离的平方值。

题解：

旋转卡壳求出凸包，然后根据单调性，求出最远两点的最大距离

 1 #pragma GCC optimize(2)
 2 #pragma G++ optimize(2)
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<cstdio>
 8 
 9 #define eps 0.00000001
10 #define N 50007
11 using namespace std;
12 inline int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
16     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 
20 int n,top;
21 double ans;
22 
23 double sqr(double x){return x*x;}
24 struct P
25 {
26     double x,y;
27     P(){}
28     P(double _x,double _y):x(_x),y(_y){}
29     friend P operator+(P a,P b){return P(a.x+b.x,a.y+b.y);}
30     friend P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}
31     friend double operator*(P a,P b){return a.x*b.y-a.y*b.x;}
32     friend double operator/(P a,P b){return a.x*b.x+a.y*b.y;}
33     friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
34     friend bool operator!=(P a,P b){return !(a==b);}
35     friend bool operator<(P a,P b)
36     {
37         if(fabs(a.y-b.y)<eps)return a.x<b.x;
38         return a.y<b.y;
39     }
40     friend double dis2(P a){return sqr(a.x)+sqr(a.y);}
41     friend void print(P a){printf("%.2lf %.2lf\n",a.x,a.y);}
42 }p[N],q[N];
43 
44 bool cmp(P a,P b)
45 {
46     if(fabs((b-p[1])*(a-p[1]))<eps)return dis2(a-p[1])<dis2(b-p[1]);
47     return (a-p[1])*(b-p[1])>0;//叉乘大于0，表示向左转，a的斜率更小。
48 }
49 void Graham()//选出凸包上的点。
50 {
51     for (int i=1;i<=n;i++)
52         if(p[i]<p[1])swap(p[i],p[1]);
53     sort(p+2,p+n+1,cmp);
54     q[++top]=p[1],q[++top]=p[2];
55     for (int i=3;i<=n;i++)
56     {
57         while((q[top]-q[top-1])*(p[i]-q[top-1])<eps&&top>1)top--;//如果当前的点的斜率更小，就替换
58         q[++top]=p[i];
59     }
60 }
61 void RC()//求直径。
62 {
63     q[top+1]=q[1];//因为凸包是一个圈。
64     int now=2;
65     for (int i=1;i<=top;i++)
66     {
67         while((q[i+1]-q[i])*(q[now]-q[i])<(q[i+1]-q[i])*(q[now+1]-q[i]))
68         {
69             now++;
70             if(now==top+1)now=1;
71         }
72         ans=max(ans,dis2(q[now]-q[i]));
73     }
74 }
75 int main()
76 {
77     n=read();
78     for (int i=1;i<=n;i++)
79         p[i].x=read(),p[i].y=read();
80     Graham();
81     RC();
82     printf("%d",(int)ans);
83 }