旋转卡壳或者直接求出来凸包之后直接枚举凸包上的点都可以，而且时间上其实差不多，理论上确实旋转卡壳比凸包要快，但是这个题看来是数据的问题，谁也不会去打个几万条边的多边形，那太费劲了

1 #include
      
         2 #include
       
          3 #include
        
           4 #define N 30005  5 #define max(a,b) a>b?a:b  6 struct point  7 {  8     long long x,y;  9 }; 10 point p[N]; 11 point sta[N]; 12 long long abs(long long a) 13 { 14     return a>=0?a:-a; 15 } 16 long long n; 17 long long dis(point p1,point p2) 18 { 19     return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y); 20 } 21 long long mul(point p1,point p2,point p3) 22 { 23     return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y); 24 } 25 int cmp(const void *a,const void *b) 26 { 27     point *c=(point *)a; 28     point *d=(point *)b; 29     long long t1=mul(p[0],*c,*d); 30     if(t1>0) 31     return -1; 32     if(t1<0) 33     return 1; 34     long long t2=dis(p[0],*d)-dis(p[0],*c); 35     if(t2>0) 36     return 1; 37     if(t2<0) 38     return -1; 39     return 0; 40 } 41 long long bag() 42 { 43     long long i,j,top=2; 44     j=0; 45     for(i=1;i
         
          1&&mul(sta[top-1],sta[top],p[i])<=0) 71         top--; 72         sta[++top]=p[i]; 73     } 74     //for(i=0;i<=top;i++) 75     //printf("%d %d\n",sta[i].x,sta[i].y); 76     return top; 77 } 78 long long rc() 79 { 80     long long CH_c=bag(); 81     long long q =1, res = 0,p; 82     //sta[++CH_c]=sta[0]; 83     for (p=0;p