poj 2187 Beauty Contest （凸包暴力求最远点对+旋转卡壳）

链接：http://poj.org/problem?id=2187

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)

============================================

没有用旋转卡壳的算法，直接暴力求的最远点对，枚举每一对点

不知是数据太弱还是暴力可以过，感觉这样可能超时，但只用了313ms

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <algorithm>

 #include <math.h>

 using namespace std;

 const int MAX=;

 const double eps=1e-;

 typedef struct point

 {

     double x,y;

 }point;

 point c[MAX];

 bool dy(double x,double y)

 {

     return x>y+eps;

 }

 bool xy(double x,double y)

 {

     return x<y-eps;

 }

 bool xyd(double x,double y)

 {

     return x<y+eps;

 }

 bool dyd(double x,double y)

 {

     return x>y-eps;

 }

 bool dd(double x,double y)

 {

     return fabs(x-y)<eps;

 }

 point stk[MAX];

 int top;

 double crossProduct(point a,point b,point c)

 {

     return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);

 }

 double dist(point a,point b)

 {

     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

 }

 double dist1(point a,point b)

 {

     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

 }

 bool cmp(point a,point b)

 {

     if(dd(a.y,b.y))

     {

         return xy(a.x,b.x);

     }

     return xy(a.y,b.y);

 }

 bool cmp1(point a,point b)

 {

      double len=crossProduct(c[],a,b);

      if(dd(len,0.0))

      {

          return xy(dist(c[],a),dist(c[],b));

      }

      return xy(len,0.0);

 }

 double solve()

 {

     double maxx=0.0;

     for(int i=;i<=top;i++)

     {

         for(int j=i+;j<=top;j++)

         {

                 if(dy(dist1(stk[i],stk[j]),maxx))

                 {

                     maxx=dist1(stk[i],stk[j]);

                 }

         }

     }

     return maxx;

 }

 double Graham(int n)

 {

     sort(c,c+n,cmp);

     sort(c+,c+n,cmp1);

     top=;

     stk[top++]=c[];

     stk[top++]=c[];

     stk[top++]=c[];

     top--;

     for(int i=;i<n;i++)

     {

         while()

         {

             point a,b;

             a=stk[top];

             b=stk[top-];

             if(xyd(crossProduct(a,b,c[i]),0.0))

             {

                 top--;

             }

             else

                 break;

         }

         stk[++top]=c[i];

     }

     return solve();

 }

 int main()

 {

     int n,i,j;

     while(scanf("%d",&n)!=EOF)

     {

          for(i=;i<n;i++)

          {

              scanf("%lf%lf",&c[i].x,&c[i].y);

          }

          if(n==)

          {

              printf("%.0lf\n",dist1(c[],c[]));

          }

          else

          {

              printf("%.0lf\n",Graham(n));

          }

     }

     return ;

 }

2014/7/27更新

旋转卡壳，卡了我两天啊，快卡死的节奏，照别人代码敲的，也不知道有没有漏掉什么，感觉凸包写的都有问题，仅供借鉴

再粘贴几个学习网址，感觉没几个人是真正理解的，包括我

http://blog.csdn.net/freezhanacmore/article/details/9527663

http://www.cnblogs.com/Booble/archive/2011/03/10/1980089.html

http://www.cnblogs.com/DreamUp/archive/2010/09/16/1828131.html

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #include <math.h>

 #include <iostream>

 #include <algorithm>

 #define eps 1e-6

 #define MAX 50010

 using namespace std;

 typedef struct point

 {

     double  x,y;

 }point;

 point c[MAX];

 int stk[MAX];

 int top;

 bool  xy(double x,double y){ return x<y-eps; }

 bool  dy(double x,double y){ return x>y+eps; }

 bool xyd(double x,double y){ return x<y+eps; }

 bool dyd(double x,double y){ return x>y-eps; }

 bool  dd(double x,double y){ return fabs(x-y)<eps; }

 double crossProduct(point a,point b,point c)

 {

     return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);

 }

 double dist(point a,point b)

 {

     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

 }

 double dist_1(point a,point b)

 {

     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

 }

 bool cmp(point a,point b)

 {

     double len=crossProduct(c[],a,b);

     if(dd(len,0.0))

     {

         return xy(dist(c[],a),dist(c[],b));

     }

     return xy(len ,0.0);

 }

 double max(double x,double y)

 {

     return xy(x,y)?y:x;//

 }

 double rotaing(int n)

 {

     int q=;

     double ans=0.0;

     stk[n]=stk[];

     for(int i=;i<n;i++)

     {

         while( xy(fabs(crossProduct(c[stk[i]],c[stk[i+]],c[stk[q]])),

                   fabs(crossProduct(c[stk[i]],c[stk[i+]],c[stk[q+]]))))

                     q=(q+)%n;

         ans=max(ans,dist_1(c[stk[i]],c[stk[q]]));

     }

     return ans;

 }

 double Graham(int n)

 {

     int tmp=;

     for(int i=;i<n;i++)

     {

         if(xy(c[i].x,c[tmp].x) || dd(c[i].x,c[tmp].x) && xy(c[i].y,c[tmp].y))

             tmp=i;

     }

     swap(c[],c[tmp]);

     sort(c+,c+n,cmp);

     stk[]=;

     stk[]=;

     top=;

     for(int i=;i<n;i++)

     {

         while( xyd(crossProduct(c[stk[top]],c[stk[top-]],c[i]),0.0)&&top>=)

         {

             top--;

         }

         stk[++top]=i;

     }

     return rotaing(top+);

 }

 int main()

 {

     int n,i,j,k,t;

     while(scanf("%d",&n)!=EOF&&n)

     {

         for(i=;i<n;i++)

         {

             scanf("%lf%lf",&c[i].x,&c[i].y);

         }

         int ans=(int )Graham(n);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

poj 2187 Beauty Contest （凸包暴力求最远点对+旋转卡壳）

最新文章

热门文章