LA 4728凸包算法-旋转卡壳的直径

  1 /*LA 4728
  2 凸包算法-旋转卡壳的直径
  3 没有其他技巧，可作为模板运用
  4 注意operator< 中精度的处理，不然会出错
  5 */
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 #include <string.h>
  9 #include <math.h>
 10 #include <ctype.h>
 11 #include <string>
 12 #include <iostream>
 13 #include <sstream>
 14 #include <vector>
 15 #include <queue>
 16 #include <stack>
 17 #include <map>
 18 #include <list>
 19 #include <set>
 20 #include <algorithm>
 21 #define INF 0x3f3f3f3f
 22 #define LL long long
 23 #define eps 1e-7
 24 #define maxn 401000
 25 using namespace std;
 26 
 27 
 28 struct Point
 29 {
 30     double x,y;
 31     Point() {}
 32     Point(LL xx,LL yy)
 33     {
 34         x=xx+0.0;
 35         y=yy+0.0;
 36     }
 37     bool operator<(const Point& p) const//注意：按照逆时针旋转
 38     {
 39         if (fabs(x-p.x)<eps) return y<p.y;//注意，这里eps一定要加，不然，不能正常排序
 40         else return x<p.x;
 41     }
 42 } P1[maxn],P2[maxn];
 43 
 44 typedef Point Vector;
 45 
 46 bool operator==(Point A,Point B)
 47 {
 48     if ((fabs(A.x-B.x)<eps) && (fabs(A.y-B.y)<eps)) return true;
 49     else return false;
 50 }
 51 Vector operator-(Point A,Point B)//表示A指向B
 52 {
 53     return Vector(A.x-B.x,A.y-B.y);
 54 }
 55 Vector operator*(Vector A,double k)
 56 {
 57     return Vector(A.x*k,A.y*k);
 58 }
 59 Vector operator+(Point A,Point B)//表示A指向B
 60 {
 61     return Vector(B.x+A.x,B.y+A.y);
 62 }
 63 double Cross(Vector A,Vector B)
 64 {
 65     return A.x*B.y-A.y*B.x;
 66 }
 67 double Area2(Point A,Point B,Point C)
 68 {
 69     return Cross(B-A,C-A);
 70 }
 71 //p是原先点的数组，n是个数，ch是凸包的点集
 72 //精度要求高是用dcmp比较
 73 //返回凸包点的个数
 74 int ConvexHull(Point *p, int n, Point* ch)         //求凸包
 75 {
 76     sort(p, p + n);//先按照x，再按照y
 77     int m = 0;
 78     for(int i = 0; i < n; i++)
 79     {
 80         while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
 81         ch[m++] = p[i];
 82     }
 83     int k = m;
 84     for(int i = n-2; i >= 0; i--)
 85     {
 86         while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
 87         ch[m++] = p[i];
 88     }
 89     if(n > 1) m--;
 90     return m;
 91 }
 92 //卡壳预备函数
 93 LL cross( const Point &o, const Point &a, const Point & b ) {
 94     return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
 95 }
 96 LL dist( const Point & a, const Point & b ) {
 97     Point p = a - b;
 98     return p.x * p.x + p.y * p.y;
 99 }
100 //计算凸包直径，输入凸包 ch，顶点个数为 n，按逆时针排列，输出直径的平方
101 LL rotating_calipers(Point *ch,int n)
102 {
103     LL q=1,ans=0;
104     ch[n]=ch[0];
105     for(int p=0; p<n; p++)
106     {
107         while(cross(ch[p],ch[p+1],ch[q+1])>cross(ch[p],ch[p+1],ch[q]))
108             q=(q+1)%n;
109         ans=max(ans,max(dist(ch[p],ch[q]),dist(ch[p+1],ch[q+1])));
110     }
111     return ans;
112 }
113 int t,n,cnt1,cnt2;
114 int main()
115 {
116     cin>>t;
117     while(t--)
118     {
119         cnt1=0;
120         cin>>n;
121         for(int i=0;i<n;i++)
122         {
123             LL x,y,w;
124             cin>>x>>y>>w;
125             P1[cnt1++]=Point(x,y);
126             P1[cnt1++]=Point(x+w,y);
127             P1[cnt1++]=Point(x,y+w);
128             P1[cnt1++]=Point(x+w,y+w);
129         }
130         cnt2=ConvexHull(P1,cnt1,P2);
131         cout<<rotating_calipers(P2,cnt2)<<endl;
132     }
133     return 0;
134 }