旋转卡壳算法；
直接在这个上面粘的模板
主要用途：用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离···
这题就是求凸包的直径
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #define eps 1e-9 7 using namespace std; 8 const double pi = acos(-1); 9 10 int dcmp(double x) 11 { 12 return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); 13 } 14 15 struct Point 16 { 17 double x; 18 double y; 19 20 Point(double x = 0, double y = 0):x(x), y(y) {} 21 22 bool operator < (const Point& e) const 23 { 24 return dcmp(x - e.x) < 0 || (dcmp(x - e.x) == 0 && dcmp(y - e.y) < 0); 25 } 26 27 bool operator == (const Point& e) const 28 { 29 return dcmp(x - e.x) == 0 && dcmp(y - e.y) == 0; 30 } 31 }; 32 33 typedef Point Vector; 34 35 Vector operator + (Point A, Point B) 36 { 37 return Vector(A.x + B.x, A.y + B.y); 38 } 39 40 Vector operator - (Point A, Point B) 41 { 42 return Vector(A.x - B.x, A.y - B.y); 43 } 44 45 Vector operator * (Point A, double p) 46 { 47 return Vector(A.x * p, A.y * p); 48 } 49 50 Vector operator / (Point A, double p) 51 { 52 return Vector(A.x / p, A.y / p); 53 } 54 double dot(Point a,Point b) 55 { 56 return a.x*b.x+a.y*b.y; 57 } 58 double cross(Point a,Point b) 59 { 60 return a.x*b.y-a.y*b.x; 61 } 62 Point rotate(Point a,double ang) 63 { 64 return Point(a.x*cos(ang)-a.y*sin(ang),a.x*sin(ang)+a.y*cos(ang)); 65 } 66 int convexhull(Point *p,int n,Point *ch) 67 { 68 sort(p,p+n); 69 int m=0; 70 for(int i=0; i<n; i++) 71 { 72 while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; 73 ch[m++]=p[i]; 74 } 75 int k=m; 76 for(int i=n-2; i>=0; i--) 77 { 78 while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; 79 ch[m++]=p[i]; 80 } 81 if(n>1)m--; 82 return m; 83 } 84 bool onsegment(Point p,Point a,Point b) 85 { 86 return dcmp(cross(a-p,b-p))==0&&dcmp(dot(a-p,b-p))<0; 87 } 88 89 90 bool SegmentProperIntersection( Point a1, Point a2, Point b1, Point b2 ) //线段相交，交点不在端点 91 { 92 double c1 = cross( a2 - a1, b1 - a1 ), c2 = cross( a2 - a1, b2 - a1 ), 93 c3 = cross( b2 - b1, a1 - b1 ), c4 = cross( b2 - b1, a2 - b1 ); 94 return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0; 95 } 96 97 int ispointinpolygon(Point p,int n,Point *poly) 98 { 99 int wn=0; 100 for(int i=0; i<n; i++) 101 { 102 if(onsegment(p,poly[i],poly[(i+1)%n]))return -1; 103 int k=dcmp(cross(poly[(i+1)%n]-poly[i],p-poly[i])); 104 int d1=dcmp(poly[i].y-p.y); 105 int d2=dcmp(poly[(i+1)%n].y-p.y); 106 if(k>0&&d1<=0&&d2>0)wn++; 107 if(k<0&&d2<=0&&d1>0)wn--; 108 } 109 if(wn!=0)return 1; 110 return 0; 111 } 112 113 bool Check(int n,Point *ch,int m,Point *th) 114 { 115 for(int i=0; i<n; i++) 116 { 117 if(ispointinpolygon(ch[i],m,th)!=0)return 1; 118 } 119 for(int i=0; i<m; i++) 120 if(ispointinpolygon(th[i],n,ch)!=0)return 1; 121 ch[n]=ch[0]; 122 th[m]=th[0]; 123 for(int i=0; i<n; i++) 124 for(int j=0; j<m; j++) 125 if(SegmentProperIntersection(ch[i],ch[i+1],th[j],th[j+1]))return 1; 126 return 0; 127 } 128 double rotating_calipers(Point *ch,int n) 129 { 130 int q=1; 131 double ans=0; 132 ch[n]=ch[0]; 133 for ( int i = 0; i < n; ++i ) 134 { 135 while ( cross( ch[i + 1] - ch[i], ch[q + 1] - ch[i] ) > cross( ch[i + 1] - ch[i], ch[q] - ch[i] ) ) 136 q = ( q + 1 ) % n; 137 ans = max( ans, max( dot( ch[i]- ch[q],ch[i]-ch[q] ),dot( ch[i + 1]-ch[q + 1],ch[i + 1]-ch[q + 1] ) )); 138 } 139 return ans; 140 } 141 Point p[400009],ch[400009]; 142 int main() 143 { 144 int n,m; 145 double x,y,w; 146 int t; 147 scanf("%d",&t); 148 while(t--) 149 { 150 scanf("%d",&n); 151 int cnt=0; 152 for(int i=0; i<n; i++) 153 { 154 scanf("%lf%lf%lf",&x,&y,&w); 155 p[cnt].x=x,p[cnt++].y=y; 156 p[cnt].x=x+w,p[cnt++].y=y; 157 p[cnt].x=x,p[cnt++].y=y+w; 158 p[cnt].x=x+w,p[cnt++].y=y+w; 159 } 160 int n1=convexhull(p,cnt,ch); 161 printf("%.0lf ",rotating_calipers(ch,n1)); 162 } 163 return 0; 164 }