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

wordpress可以放视频播放器/长沙网站托管seo优化公司

news 2025/8/4 2:11:22

wordpress可以放视频播放器,长沙网站托管seo优化公司,nx二次开发,建一个团购网站要多少钱旋转卡壳或者直接求出来凸包之后直接枚举凸包上的点都可以，而且时间上其实差不多，理论上确实旋转卡壳比凸包要快，但是这个题看来是数据的问题，谁也不会去打个几万条边的多边形，那太费劲了 View Code 1 #include<st…

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

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  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<n;i++)
 46     {
 47         if(p[i].y<p[j].y)
 48         {
 49             j=i;
 50         }
 51         else if(p[i].y==p[j].y)
 52         {
 53             if(p[i].x<p[j].x)
 54             j=i;
 55         }
 56     }
 57     if(j)
 58     {
 59         point temp;
 60         temp=p[0];
 61         p[0]=p[j];
 62         p[j]=temp;
 63     }
 64     qsort(p+1,n-1,sizeof(p[0]),cmp);
 65     sta[0]=p[0];
 66     sta[1]=p[1];
 67     sta[2]=p[2];
 68     for(i=3;i<n;i++)
 69     {
 70         while(top>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<CH_c;++p)
 84     {
 85         while(mul(sta[p],sta[p+1],sta[q])<mul(sta[p],sta[p+1],sta[q+1]))
 86             q=(q+1)%CH_c;
 87         //fprintf(stderr, "%d %d\n", p, q);
 88         res=max(res,dis(sta[p],sta[q]));
 89         res=max(res,dis(sta[p+1],sta[q+1])); //On condition that two edges parrels(?)
 90     }
 91     return res;
 92 
 93 }
 94 int main()
 95 {
 96     long long i,j,k;
 97     long long di;
 98     while(scanf("%lld",&n)!=EOF)
 99     {
100         di=0;
101         for(i=0;i<n;i++)
102         scanf("%lld%lld",&p[i].x,&p[i].y);
103         printf("%lld\n",rc());
104     }
105     return 0;
106 }