Beauty Contest(旋转卡壳模版题)

Beauty Contest

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 44329		Accepted: 13668

Description

Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates.

Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.

Input

* Line 1: A single integer, N

* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm

Output

* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.

Sample Input

Sample Output

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<vector>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 const double eps=1e-8;
  9 const double INF=1e20;
 10 const double PI=acos(-1.0);
 11 
 12 int sgn(double x){
 13     if(fabs(x)<eps) return 0;
 14     if(x<0) return -1;
 15     else return 1;
 16 }
 17 
 18 inline double sqr(double x){return x*x;}
 19 inline double hypot(double a,double b){return sqrt(a*a+b*b);}
 20 struct Point{
 21     double x,y;
 22     Point(){}
 23     Point(double _x,double _y){
 24         x=_x;
 25         y=_y;
 26     }
 27     void input(){
 28         scanf("%lf %lf",&x,&y);
 29     }
 30     void output(){
 31         printf("%.2f %.2f
",x,y);
 32     }
 33     bool operator == (const Point &b)const{
 34         return sgn(x-b.x) == 0 && sgn(y-b.y)== 0;
 35     }
 36     bool operator < (const Point &b)const{
 37         return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
 38     }
 39     Point operator - (const Point &b)const{
 40         return Point(x-b.x,y-b.y);
 41     }
 42     //叉积
 43     double operator ^ (const Point &b)const{
 44         return x*b.y-y*b.x;
 45     }
 46     //点积
 47     double operator * (const Point &b)const{
 48         return x*b.x+y*b.y;
 49     }
 50     //返回长度
 51     double len(){
 52         return hypot(x,y);
 53     }
 54     //返回长度的平方
 55     double len2(){
 56         return x*x+y*y;
 57     }
 58     //返回两点的距离
 59     double distance(Point p){
 60         return hypot(x-p.x,y-p.y);
 61     }
 62     Point operator + (const Point &b)const{
 63         return Point(x+b.x,y+b.y);
 64     }
 65     Point operator * (const double &k)const{
 66         return Point(x*k,y*k);
 67     }
 68     Point operator / (const double &k)const{
 69         return Point(x/k,y/k);
 70     }
 71 
 72     //计算pa和pb的夹角
 73     //就是求这个点看a,b所成的夹角
 74     ///LightOJ1202
 75     double rad(Point a,Point b){
 76         Point p=*this;
 77         return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
 78     }
 79     //化为长度为r的向量
 80     Point trunc(double r){
 81         double l=len();
 82         if(!sgn(l)) return *this;
 83         r/=l;
 84         return Point(x*r,y*r);
 85     }
 86     //逆时针转90度
 87     Point rotleft(){
 88         return Point(-y,x);
 89     }
 90     //顺时针转90度
 91     Point rotright(){
 92         return Point(y,-x);
 93     }
 94     //绕着p点逆时针旋转angle
 95     Point rotate(Point p,double angle){
 96         Point v=(*this) -p;
 97         double c=cos(angle),s=sin(angle);
 98         return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
 99     }
100 };
101 
102 struct Line{
103     Point s,e;
104     Line(){}
105     Line(Point _s,Point _e){
106         s=_s;
107         e=_e;
108     }
109     bool operator==(Line v){
110         return (s==v.s)&&(e==v.e);
111     }
112     //根据一个点和倾斜角angle确定直线，0<=angle<pi
113     Line(Point p,double angle){
114         s=p;
115         if(sgn(angle-PI/2)==0){
116             e=(s+Point(0,1));
117         }
118         else{
119             e=(s+Point(1,tan(angle)));
120         }
121     }
122     //ax+by+c=0;
123     Line(double a,double b,double c){
124         if(sgn(a)==0){
125             s=Point(0,-c/b);
126             e=Point(1,-c/b);
127         }
128         else if(sgn(b)==0){
129             s=Point(-c/a,0);
130             e=Point(-c/a,1);
131         }
132         else{
133             s=Point(0,-c/b);
134             e=Point(1,(-c-a)/b);
135         }
136     }
137     void input(){
138         s.input();
139         e.input();
140     }
141     void adjust(){
142         if(e<s) swap(s,e);
143     }
144     //求线段长度
145     double length(){
146         return s.distance(e);
147     }
148     //返回直线倾斜角 0<=angle<pi
149     double angle(){
150         double k=atan2(e.y-s.y,e.x-s.x);
151         if(sgn(k)<0) k+=PI;
152         if(sgn(k-PI)==0) k-=PI;
153         return k;
154     }
155     //点和直线的关系
156     //1 在左侧
157     //2 在右侧
158     //3 在直线上
159     int relation(Point p){
160         int c=sgn((p-s)^(e-s));
161         if(c<0) return 1;
162         else if(c>0) return 2;
163         else return 3;
164     }
165     //点在线段上的判断
166     bool pointonseg(Point p){
167         return sgn((p-s)^(e-s))==0&&sgn((p-s)*(p-e))<=0;
168     }
169     //两向量平行(对应直线平行或重合)
170     bool parallel(Line v){
171         return sgn((e-s)^(v.e-v.s))==0;
172     }
173     //两线段相交判断
174     //2 规范相交
175     //1 非规范相交
176     //0 不相交
177     int segcrossseg(Line v){
178         int d1=sgn((e-s)^(v.s-s));
179         int d2=sgn((e-s)^(v.e-s));
180         int d3=sgn((v.e-v.s)^(s-v.s));
181         int d4=sgn((v.e-v.s)^(e-v.s));
182         if((d1^d2)==-2&&(d3^d4)==-2) return 2;
183         return (d1==0&&sgn((v.s-s)*(v.s-e))<=0||
184                 d2==0&&sgn((v.e-s)*(v.e-e))<=0||
185                 d3==0&&sgn((s-v.s)*(s-v.e))<=0||
186                 d4==0&&sgn((e-v.s)*(e-v.e))<=0);
187     }
188     //直线和线段相交判断
189     //-*this line -v seg
190     //2 规范相交
191     //1 非规范相交
192     //0 不相交
193     int linecrossseg(Line v){
194         int d1=sgn((e-s)^(v.s-s));
195         int d2=sgn((e-s)^(v.e-s));
196         if((d1^d2)==-2) return 2;
197         return (d1==0||d2==0);
198     }
199     //两直线关系
200     //0 平行
201     //1 重合
202     //2 相交
203     int linecrossline(Line v){
204         if((*this).parallel(v))
205             return v.relation(s)==3;
206         return 2;
207     }
208     //求两直线的交点
209     //要保证两直线不平行或重合
210     Point crosspoint(Line v){
211         double a1=(v.e-v.s)^(s-v.s);
212         double a2=(v.e-v.s)^(e-v.s);
213         return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
214     }
215     //点到直线的距离
216     double dispointtoline(Point p){
217         return fabs((p-s)^(e-s))/length();
218     }
219     //点到线段的距离
220     double dispointtoseg(Point p){
221         if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0)
222             return min(p.distance(s),p.distance(e));
223         return dispointtoline(p);
224     }
225     //返回线段到线段的距离
226     //前提是两线段不相交，相交距离就是0了
227     double dissegtoseg(Line v){
228         return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
229     }
230     //返回点P在直线上的投影
231     Point lineprog(Point p){
232         return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
233     }
234     //返回点P关于直线的对称点
235     Point symmetrypoint(Point p){
236         Point q=lineprog(p);
237         return Point(2*q.x-p.x,2*q.y-p.y);
238     }
239 };
240 
241 struct circle{
242     Point p;
243     double r;
244     circle(){}
245     circle(Point _p,double _r){
246         p=_p;
247         r=_r;
248     }
249 
250     circle(double x,double y,double _r){
251         p=Point(x,y);
252         r=_r;
253     }
254 
255     circle(Point a,Point b,Point c){///三角形的外接圆
256         Line u=Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
257         Line v=Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
258         p=u.crosspoint(v);
259         r=p.distance(a);
260     }
261 
262     circle(Point a,Point b,Point c,bool t){///三角形的内切圆
263         Line u,v;
264         double m=atan2(b.y-a.y,b.x-a.x),n=atan2(c.y-a.y,c.x-a.x);
265         u.s=a;
266         u.e=u.s+Point(cos((n+m)/2),sin((n+m)/2));
267         v.s=b;
268         m=atan2(a.y-b.y,a.x-b.x),n=atan2(c.y-b.y,c.x-b.x);
269         v.e=v.s+Point(cos((n+m)/2),sin((n+m)/2));
270         p=u.crosspoint(v);
271         r=Line(a,b).dispointtoseg(p);
272     }
273 
274     void input(){
275         p.input();
276         scanf("%lf",&r);
277     }
278 
279     void output(){
280         printf("%.2f %.2f %.2f
",p.x,p.y,r);
281     }
282 
283     bool operator==(circle v){
284         return (p==v.p)&&sgn(r-v.r)==0;
285     }
286 
287     bool operator<(circle v)const{
288         return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
289     }
290 
291     double area(){
292         return PI*r*r;
293     }
294 
295     double circumference(){ ///周长
296         return 2*PI*r;
297     }
298 
299     int relation(Point b){///点和圆的关系  0圆外  1圆上  2圆内
300         double dst=b.distance(p);
301         if(sgn(dst-r)<0) return 2;
302         else if(sgn(dst-r)==0) return 1;
303         return 0;
304     }
305 
306     int relationseg(Line v){///线段和圆的关系，比较的是圆心到线段的距离和半径的关系
307         double dst=v.dispointtoseg(p);
308         if(sgn(dst-r)<0) return 2;
309         else if(sgn(dst-r)==0) return 1;
310         return 0;
311     }
312 
313     int relationline(Line v){///直线和圆的关系，比较的是圆心到直线的距离和半径的关系
314         double dst=v.dispointtoline(p);
315         if(sgn(dst-r)<0) return 2;
316         else if(sgn(dst-r)==0) return 1;
317         return 0;
318     }
319 
320     int relationcircle(circle v){///两圆的关系  5相离 4外切 3相交 2内切 1内含
321         double d=p.distance(v.p);
322         if(sgn(d-r-v.r)>0) return 5;
323         if(sgn(d-r-v.r)==0) return 4;
324         double l=fabs(r-v.r);
325         if(sgn(d-r-v.r)<0&&sgn(d-l)>0) return 3;
326         if(sgn(d-l)==0) return 2;
327         if(sgn(d-l)<0)  return 1;
328     }
329 
330     int pointcrosscircle(circle v,Point &p1,Point &p2){///求两个圆的交点，0没有交点 1一个交点 2两个交点
331         int rel=relationcircle(v);
332         if(rel == 1 || rel == 5) return 0;
333         double d=p.distance(v.p);
334         double l=(d*d+r*r-v.r*v.r)/2*d;
335         double h=sqrt(r*r-l*l);
336         Point tmp=p+(v.p-p).trunc(l);
337         p1=tmp+((v.p-p).rotleft().trunc(h));
338         p2=tmp+((v.p-p).rotright().trunc(h));
339         if(rel == 2 || rel == 4) return 1;
340         return 2;
341     }
342 
343     int pointcrossline(Line v,Point &p1,Point &p2){///求直线和圆的交点，返回交点的个数
344         if(!(*this).relationline(v)) return 0;
345         Point a=v.lineprog(p);
346         double d=v.dispointtoline(p);
347         d=sqrt(r*r-d*d);
348         if(sgn(d)==0) {
349             p1=a;
350             p2=a;
351             return 1;
352         }
353         p1=a+(v.e-v.s).trunc(d);
354         p2=a-(v.e-v.s).trunc(d);
355         return 2;
356     }
357 
358     int getcircle(Point a,Point b,double r1,circle &c1,circle &c2){///得到过a，b两点，半径为r1的两个圆
359         circle x(a,r1),y(b,r1);
360         int t=x.pointcrosscircle(y,c1.p,c2.p);
361         if(!t) return 0;
362         c1.r=c2.r=r;
363         return t;
364     }
365 
366     int getcircle(Line u,Point q,double r1,circle &c1,circle &c2){///得到与直线u相切，过点q，半径为r1的圆
367         double dis = u.dispointtoline(q);
368         if(sgn(dis-r1*2)>0) return 0;
369         if(sgn(dis)==0) {
370             c1.p=q+((u.e-u.s).rotleft().trunc(r1));
371             c2.p=q+((u.e-u.s).rotright().trunc(r1));
372             c1.r=c2.r=r1;
373             return 2;
374         }
375         Line u1=Line((u.s+(u.e-u.s).rotleft().trunc(r1)),(u.e+(u.e-u.s).rotleft().trunc(r1)));
376         Line u2=Line((u.s+(u.e-u.s).rotright().trunc(r1)),(u.e+(u.e-u.s).rotright().trunc(r1)));
377         circle cc=circle(q,r1);
378         Point p1,p2;
379         if(!cc.pointcrossline(u1,p1,p2)) cc.pointcrossline(u2,p1,p2);
380         c1=circle(p1,r1);
381         if(p1==p2){
382             c2=c1;
383             return 1;
384         }
385         c2=circle(p2,r1);
386         return 2;
387     }
388 
389     int getcircle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){///同时与直线u，v相切，半径为r1的圆
390         if(u.parallel(v)) return 0;///两直线平行
391         Line u1=Line(u.s+(u.e-u.s).rotleft().trunc(r1),u.e+(u.e-u.s).rotleft().trunc(r1));
392         Line u2=Line(u.s+(u.e-u.s).rotright().trunc(r1),u.e+(u.e-u.s).rotright().trunc(r1));
393         Line v1=Line(v.s+(v.e-v.s).rotleft().trunc(r1),v.e+(v.e-v.s).rotleft().trunc(r1));
394         Line v2=Line(v.s+(v.e-v.s).rotright().trunc(r1),v.e+(v.e-v.s).rotright().trunc(r1));
395         c1.r=c2.r=c3.r=c4.r=r1;
396         c1.p=u1.crosspoint(v1);
397         c2.p=u1.crosspoint(v2);
398         c3.p=u2.crosspoint(v1);
399         c4.p=u2.crosspoint(v2);
400         return 4;
401     }
402 
403     int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2){///同时与不相交圆 cx,cy相切，半径为r1的圆
404         circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
405         int t=x.pointcrosscircle(y,c1.p,c2.p);
406         if(!t) return 0;
407         c1.r=c2.r=r1;
408         return t;
409     }
410 
411     int tangentline(Point q,Line &u,Line &v){///过一点作圆的切线（先判断点和圆的关系）
412         int x=relation(q);
413         if(x==2) return 0;
414         if(x==1){
415             u=Line(q,q+(q-p).rotleft());
416             v=u;
417             return 1;
418         }
419         double d=p.distance(q);
420         double l=r*r/d;
421         double h=sqrt(r*r-l*l);
422         u=Line(q,p+((q-p).trunc(l)+(q-p).rotleft().trunc(h)));
423         v=Line(q,p+((q-p).trunc(l)+(q-p).rotright().trunc(h)));
424         return 2;
425     }
426 
427     double areacircle(circle v){///求两圆相交的面积
428         int rel=relationcircle(v);
429         if(rel >= 4) return 0.0;
430         if(rel <= 2) return min(area(),v.area());
431         double d=p.distance(v.p);
432         double hf=(r+v.r+d)/2.0;
433         double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
434         double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
435         a1=a1*r*r;
436         double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
437         a2=a2*v.r*v.r;
438         return a1+a2-ss;
439     }
440 
441     double areatriangle(Point a,Point b){///求圆和三角形pab的相交面积
442         if(sgn((p-a)^(p-b))==0) return 0.0;
443         Point q[5];
444         int len=0;
445         q[len++]=a;
446         Line l(a,b);
447         Point p1,p2;
448         if(pointcrossline(l,q[1],q[2])==2){
449             if(sgn((a-q[1])*(b-q[1]))<0) q[len++]=q[1];
450             if(sgn((a-q[2])*(b-q[2]))<0) q[len++]=q[2];
451         }
452         q[len++]=b;
453         if(len==4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0) swap(q[1],q[2]);
454         double res=0;
455         for(int i=0;i<len-1;i++){
456             if(relation(q[i])==0||relation(q[i+1])==0){
457                 double arg=p.rad(q[i],q[i+1]);
458                 res+=r*r*arg/2.0;
459             }
460             else{
461                 res+=fabs((q[i]-p)^(q[i+1]-p))/2.0;
462             }
463         }
464         return res;
465     }
466 };
467 
468 struct polygon{
469     int n;
470     Point p[100010];
471     Line l[100010];
472     void input(int _n){
473         n=_n;
474         for(int i=0;i<n;i++){
475             p[i].input();
476         }
477     }
478 
479     void add(Point q){
480         p[n++]=q;
481     }
482 
483     void getline(){
484         for(int i=0;i<n;i++){
485             l[i]=Line(p[i],p[(i+1)%n]);
486         }
487     }
488 
489     struct cmp{
490         Point p;
491         cmp(const Point &p0){p=p0;}
492         bool operator()(const Point &aa,const Point &bb){
493             Point a=aa,b=bb;
494             int d=sgn((a-p)^(b-p));
495             if(d==0){
496                 return sgn(a.distance(p)-b.distance(p))<0;
497             }
498             return d>0;
499         }
500     };
501 
502     void norm(){///进行极角排序
503         Point mi=p[0];
504         for(int i=1;i<n;i++){
505             mi=min(mi,p[i]);
506         }
507         sort(p,p+n,cmp(mi));
508     }
509 
510     void getconvex(polygon &convex){///得到第一种凸包的方法，编号为0～n-1，可能要特判所有点共点或共线的特殊情况
511         sort(p,p+n);
512         convex.n=n;
513         for(int i=0;i<min(n,2);i++){
514             convex.p[i]=p[i];
515         }
516         if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
517         if(n<=2) return;
518         int &top=convex.n;
519         top=1;
520         for(int i=2;i<n;i++){
521             while(top&&sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0) top--;
522             convex.p[++top]=p[i];
523         }
524         int temp=top;
525         convex.p[++top]=p[n-2];
526         for(int i=n-3;i>=0;i--){
527             while(top!=temp&&sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0) top--;
528             convex.p[++top]=p[i];
529         }
530         if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
531         convex.norm();
532     }
533 
534     void Graham(polygon &convex){///得到凸包的第二种方法
535         norm();
536         int &top=convex.n;
537         top=0;
538         if(n==1){
539             top=1;
540             convex.p[0]=p[0];
541             return;
542         }
543         if(n==2){
544             top=2;
545             convex.p[0]=p[0];
546             convex.p[1]=p[1];
547             if(convex.p[0]==convex.p[1]) top--;
548             return;
549         }
550         convex.p[0]=p[0];
551         convex.p[1]=p[1];
552         top=2;
553         for(int i=2;i<n;i++){
554             while(top>1&&sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0) top--;
555             convex.p[top++]=p[i];
556         }
557         if(convex.n==2 && (convex.p[0]==convex.p[1])) convex.n--;
558     }
559 
560     double rotating_calipers(){
561         double ans = 0;
562         Point v;
563         int cur = 1;
564         for (int i = 0; i < n; i++){
565             v = p[i] - p[(i + 1) % n];
566             while ((v ^ (p[(cur + 1) % n] - p[cur])) < 0){
567                 cur = (cur + 1) % n;
568             }
569             ans = max(ans, max((p[i]-p[cur]).len2(),(p[(i+1)%n]-p[(cur+1)%n]).len2()));
570         }
571         return ans;
572     }
573 
574     bool inconvex(){///判断是不是凸的
575         bool s[3];
576         memset(s,false,sizeof(s));
577         for(int i=0;i<n;i++){
578             int j=(i+1)%n;
579             int k=(j+1)%n;
580             s[sgn((p[j]-p[i])^(p[k]-p[i]))+1]=true;
581             if(s[0]&&s[2]) return false;
582         }
583         return true;
584     }
585 
586     int relationpoint(Point q){///判断点和任意多边形的关系  3点上 2边上 1内部 0外部
587         for(int i=0;i<n;i++){
588             if(p[i]==q) return 3;
589         }
590         getline();
591         for(int i=0;i<n;i++){
592             if(l[i].pointonseg(q)) return 2;
593         }
594         int cnt=0;
595         for(int i=0;i<n;i++){
596             int j=(i+1)%n;
597             int k=sgn((q-p[j])^(p[i]-p[j]));
598             int u=sgn(p[i].y-q.y);
599             int v=sgn(p[j].y-q.y);
600             if(k>0&&u<0&&v>=0) cnt++;
601             if(k<0&&v<0&&u>=0) cnt--;
602         }
603         return cnt!=0;
604     }
605 
606     void convexcnt(Line u,polygon &po){///直线u切割凸多边形左侧  注意直线方向
607         int &top=po.n;
608         top=0;
609         for(int i=0;i<n;i++){
610             int d1=sgn((u.e-u.s)^(p[i]-u.s));
611             int d2=sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
612             if(d1>=0) po.p[top++]=p[i];
613             if(d1*d2<0)po.p[top++]=u.crosspoint(Line(p[i],p[(i+1)%n]));
614         }
615     }
616 
617     double getcircumference(){///得到周长
618         double sum=0;
619         for(int i=0;i<n;i++){
620             sum+=p[i].distance(p[(i+1)%n]);
621         }
622         return sum;
623     }
624 
625     double getarea(){///得到面积
626         double sum=0;
627         for(int i=0;i<n;i++){
628             sum+=(p[i]^p[(i+1)%n]);
629         }
630         return fabs(sum)/2;
631     }
632 
633     bool getdir(){///得到方向 1表示逆时针  0表示顺时针
634         double sum=0;
635         for(int i=0;i<n;i++){
636             sum+=(p[i]^p[(i+1)%n]);
637         }
638         if(sgn(sum)>0) return 1;
639         return 0;
640     }
641 
642     Point getbarycentre(){///得到重心
643         Point ret(0,0);
644         double area=0;
645         for(int i=1;i<n-1;i++){
646             double tmp=(p[i]-p[0])^(p[i+1]-p[0]);
647             if(sgn(tmp)==0) continue;
648             area+=tmp;
649             ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
650             ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
651         }
652         if(sgn(area)) ret =ret/area;
653         return ret;
654     }
655 
656     double areacircle(circle c){///多边形和圆交的面积
657         double ans=0;
658         for(int i=0;i<n;i++){
659             int j=(i+1)%n;
660             if(sgn((p[j]-c.p)^(p[i]-c.p))>=0) ans+=c.areatriangle(p[i],p[j]);
661             else ans-=c.areatriangle(p[i],p[j]);
662         }
663         return fabs(ans);
664     }
665 
666     int relationcircle(circle c){///多边形和圆的关系 2圆完全在多边形内  1圆在多边形里面，碰到了多边形的边界  0其他
667         getline();
668         int x=2;
669         if(relationpoint(c.p)!=1) return 0;
670         for(int i=0;i<n;i++){
671             if(c.relationseg(l[i])==2) return 0;
672             if(c.relationseg(l[i])==1) x=1;
673         }
674         return x;
675     }
676 };
677 
678 double cross(Point a,Point b,Point c){///ab x ac
679     return (b-a)^(c-a);
680 }
681 
682 double dot(Point a,Point b,Point c){///ab*ac;
683     return (b-a)*(c-a);
684 }
685 
686 double minRectangleCover(polygon A){///`最小矩形面积覆盖`,` A 必须是凸包(而且是逆时针顺序)`,` 测试 UVA 10173`
687     //`要特判A.n < 3的情况`
688     if(A.n < 3)return 0.0;
689     A.p[A.n] = A.p[0];
690     double ans = -1;
691     int r = 1, p = 1, q;
692     for(int i = 0;i < A.n;i++){
693         //`卡出离边A.p[i] - A.p[i+1]最远的点`
694         while( sgn( cross(A.p[i],A.p[i+1],A.p[r+1]) - cross(A.p[i],A.p[i+1],A.p[r]) ) >= 0 )
695             r = (r+1)%A.n;
696         //`卡出A.p[i] - A.p[i+1]方向上正向n最远的点`
697         while(sgn( dot(A.p[i],A.p[i+1],A.p[p+1]) - dot(A.p[i],A.p[i+1],A.p[p]) ) >= 0 )
698             p = (p+1)%A.n;
699         if(i == 0)q = p;
700         //`卡出A.p[i] - A.p[i+1]方向上负向最远的点`
701         while(sgn(dot(A.p[i],A.p[i+1],A.p[q+1]) - dot(A.p[i],A.p[i+1],A.p[q])) <= 0)
702             q = (q+1)%A.n;
703         double d = (A.p[i] - A.p[i+1]).len2();
704         double tmp = cross(A.p[i],A.p[i+1],A.p[r]) *
705             (dot(A.p[i],A.p[i+1],A.p[p]) - dot(A.p[i],A.p[i+1],A.p[q]))/d;
706         if(ans < 0 || ans > tmp)ans = tmp;
707     }
708     return ans;
709 }
710 
711 vector<Point> convexCut(const vector<Point>&ps,Point q1,Point q2){///直线切凸多边形，多边形是逆时针的，在q1q2的左侧
712     vector<Point>qs;
713     int n=ps.size();
714     for(int i=0;i<n;i++){
715         Point p1=ps[i],p2=ps[(i+1)%n];
716         int d1=sgn((q2-q1)^(p1-q1)),d2=sgn((q2-q1)^(p2-q1));
717         if(d1>=0) qs.push_back(p1);
718         if(d1*d2<0) qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
719     }
720     return qs;
721 }
722 
723 struct halfplane:public Line{
724     double angle;
725     halfplane(){}
726     halfplane(Point _s,Point _e){///表示向量s->e逆时针（左侧）的半平面
727         s=_s;
728         e=_e;
729     }
730     halfplane(Line v){
731         s=v.s;
732         e=v.e;
733     }
734     void calcangle(){
735         angle=atan2(e.y-s.y,e.x-s.x);
736     }
737     bool operator<(const halfplane &b)const{
738         return angle<b.angle;
739     }
740 };
741 
742 struct halfplanes{
743     int n;
744     halfplane hp[2020];
745     Point p[2020];
746     int que[2020];
747     int st,ed;
748     void push(halfplane tmp){
749         hp[n++]=tmp;
750     }
751 
752     void unique(){///去重
753         int m=1;
754         for(int i=1;i<n;i++){
755             if(sgn(hp[i].angle-hp[i-1].angle)!=0) hp[m++]=hp[i];
756             else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0) hp[m-1]=hp[i];
757         }
758         n=m;
759     }
760     bool halfplaneinsert(){
761         for(int i=0;i<n;i++) hp[i].calcangle();
762         sort(hp,hp+n);
763         unique();
764         que[st=0]=0;
765         que[ed=1]=1;
766         p[1]=hp[0].crosspoint(hp[1]);
767         for(int i=2;i<n;i++){
768             while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--;
769             while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++;
770             que[++ed]=i;
771             if(hp[i].parallel(hp[que[ed-1]])) return false;
772             p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
773         }
774         while(st<ed&&sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--;
775         while(st<ed&&sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++;
776         if(st+1>=ed) return false;
777         return true;
778     }
779 
780     void getconvex(polygon &con){///得到最后半平面交得到的凸多边形，要先调用halfplaneinsert()且返回true
781         p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
782         con.n=ed-st+1;
783         for(int j=st,i=0;j<=ed;i++,j++){
784             con.p[i]=p[j];
785         }
786     }
787 };
788 
789 struct circles{
790     circle c[1010];
791     double ans[1010];///ans[i]表示被覆盖了i次的面积
792     double pre[1010];
793     int n;
794     circles(){}
795     void add(circle cc){
796         c[n++]=cc;
797     }
798 
799     bool inner(circle x,circle y){///x包含在y中
800         if(x.relationcircle(y)!=1) return 0;
801         return sgn(x.r-y.r)<=0?1:0;
802     }
803 
804     void init_or(){///圆的面积并去掉内含的圆
805         bool mark[1010]={0};
806         int i,j,k=0;
807         for(i=0;i<n;i++){
808             for(j=0;j<n;j++){
809                 if(i!=j&&!mark[j]){
810                     if(c[i]==c[j]||inner(c[i],c[j])) break;
811                 }
812             }
813             if(j<n) mark[i]=1;
814         }
815         for(i=0;i<n;i++){
816             if(!mark[i]) c[k++]=c[i];
817         }
818         n=k;
819     }
820 
821     void init_add(){///圆的面积交去掉内含的圆
822         int i,j,k;
823         bool mark[1010]={0};
824         for(i=0;i<n;i++){
825             for(int j=0;j<n;j++){
826                 if(i!=j&&!mark[j]){
827                     if((c[i]==c[j])||inner(c[j],c[i])) break;
828                 }
829             }
830             if(j<n) mark[i]=1;
831         }
832         for(i=0;i<n;i++){
833             if(!mark[i]){
834                 c[k++]=c[i];
835             }
836         }
837         n=k;
838     }
839 
840     double areaarc(double th,double r){///半径为r的圆，弧度为th，对应的弓形的面积
841         return 0.5*r*r*(th-sin(th));
842     }
843 
844 
845     void getarea(){
846         memset(ans,0,sizeof(ans));
847         vector<pair<double,int> >v;
848         for(int i=0;i<n;i++){
849             v.clear();
850             v.push_back(make_pair(-PI,1));
851             v.push_back(make_pair(PI,-1));
852             for(int j=0;j<n;j++){
853                 if(i!=j){
854                     Point q=(c[j].p-c[i].p);
855                     double ab=q.len(),ac=c[i].r,bc=c[j].r;
856                     if(sgn(ab+ac-bc)<=0){
857                         v.push_back(make_pair(-PI,1));
858                         v.push_back(make_pair(PI,-1));
859                         continue;
860                     }
861                     if(sgn(ab+bc-ac)<=0)continue;
862                     if(sgn(ab-ac-bc)>0) continue;
863                     double th=atan2(q.y,q.x),fai=acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
864                     double a0=th-fai;
865                     if(sgn(a0+PI)<0) a0+=2*PI;
866                     double a1=th+fai;
867                     if(sgn(a1-PI)>0) a1-=2*PI;
868                     if(sgn(a0-a1)>0){
869                         v.push_back(make_pair(a0,1));
870                         v.push_back(make_pair(PI,-1));
871                         v.push_back(make_pair(-PI,1));
872                         v.push_back(make_pair(a1,-1));
873                     }
874                     else{
875                         v.push_back(make_pair(a0,1));
876                         v.push_back(make_pair(a1,-1));
877                     }
878                 }
879                 sort(v.begin(),v.end());
880                 int cur=0;
881                 for(int j=0;j<v.size();j++){
882                     if(cur&&sgn(v[j].first-pre[cur])){
883                         ans[cur]+=areaarc(v[j].first-pre[cur],c[i].r);
884                         ans[cur]+=0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
885                     }
886                     cur+=v[j].second;
887                     pre[cur]=v[j].first;
888                 }
889             }
890         }
891         for(int i=1;i<n;i++){
892             ans[i]-=ans[i+1];
893         }
894     }
895 };
896 
897 
898 
899 bool Check(Line a,Line b){
900     if(sgn((a.s-a.e)^(b.s-a.e))*sgn((a.s-a.e)^(b.e-a.e))>0) return false;
901     if(sgn((b.s-b.e)^(a.s-b.e))*sgn((b.s-b.e)^(a.e-b.e))>0) return false;
902     if(sgn(max(a.s.x,a.e.x)-min(b.s.x,b.e.x))>=0&&sgn(max(b.s.x,b.e.x)-min(a.s.x,a.e.x))>=0
903      &&sgn(max(a.s.y,a.e.y)-min(b.s.y,b.e.y))>=0&&sgn(max(b.s.y,b.e.y)-min(a.s.y,a.e.y))>=0)
904         return true;
905     else return false;
906 }
907 
908 int n;
909 polygon poly,tmp;
910 
911 
912 double dis(Point a,Point b){
913     return a.distance(b);
914 }
915 
916 
917 void change(Point a,Point b,Point &c,Point &d,double p)///将线段ab往左移动距离p
918 {
919     double len = a.distance(b);
920     double dx = (a.y - b.y)*p/len;
921     double dy = (b.x - a.x)*p/len;
922     c.x = a.x + dx; c.y = a.y + dy;
923     d.x = b.x + dx; d.y = b.y + dy;
924 }
925 
926 void get_equation(Point p1,Point p2,double &a,double &b,double &c){///通过两点求直线方程
927     a=p2.y-p1.y;
928     b=p1.x-p2.x;
929     c=p2.x*p1.y-p1.x*p2.y;
930 }
931 
932 Point Intersection(Point p1,Point p2,double a,double b,double c){///求交点
933     double u = fabs(a*p1.x + b*p1.y + c);
934     double v = fabs(a*p2.x + b*p2.y + c);
935     Point t;
936     t.x = (p1.x*v + p2.x*u)/(u+v);
937     t.y = (p1.y*v + p2.y*u)/(u+v);
938     return t;
939 }
940 
941 
942 int main(){
943      int n;
944      while(~scanf("%d",&n)){
945         poly.input(n);
946         poly.getconvex(tmp);
947         printf("%lld
",(long long)tmp.rotating_calipers());
948      }
949     return 0;
950 }

View Code