poj 2187 Beauty Contest

Beauty Contest

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 26087		Accepted: 8044

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)

Source

另加两组测试数据

5
-2 0
-1 0
0 0
1 0
2 0 答案16

4
-1 0
0 0
1 0
2 0 答案 9

要注意多个点共线的情况。

题意：给你n个点，求相距最长的距离的平方。

这是一个凸包的模板题，就是这样一个模板题，错了几次。

慢慢的看，我发现自己对凸包理解的不够清晰。这个是很要命的。

代码中，dis和distance1的效果是一样的，用后者就好了。

特殊的举例，包含了多个点平行的时候的情况，所以要考虑到这个情况。

那什么什么旋转的方法，没有学到。(⊙o⊙)…，待续。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 struct node
10 {
11    int x,y;
12 };
13 node a[50002],stack1[50002];
14 double dis(node n1,node n2)
15 {
16     return (double)sqrt( (n1.x-n2.x)*(n1.x-n2.x)*1.0 + (n1.y-n2.y)*(n1.y-n2.y)*1.0 );
17 }
18 int distance1(node n1,node n2)
19 {
20     return  (n1.x-n2.x)*(n1.x-n2.x) + (n1.y-n2.y)*(n1.y-n2.y);
21 }
22 
23 double cross(node a,node n1,node n2)
24 {
25     return (n1.x-a.x)*(n2.y-a.y) - (n1.y-a.y)*(n2.x-a.x);
26 }
27 bool cmp(node n1,node n2)
28 {
29     double k = cross(a[0],n1,n2);
30     if( k>0) return true;
31     else if( k==0 && dis(a[0],n1)<dis(a[0],n2))
32         return true;
33     else return false;
34 }
35 void tom(node *ch,int n)
36 {
37    int i,ans=0,j;
38    for(i=0;i<=n;i++)
39     for(j=i+1;j<=n;j++)
40    {
41        ans=max(ans,distance1(ch[i],ch[j]));
42    }
43    printf("%d
",ans);
44 }
45 void Graham(int n)
46 {
47     int i,head;
48     for(i=1;i<n;i++)
49         if(a[i].x<a[0].x ||(a[i].x==a[0].x&&a[i].y<a[0].y ) )
50             swap(a[0],a[i]);
51     sort(a+1,a+n,cmp);
52     a[n]=a[0];
53     stack1[0]=a[0];
54     stack1[1]=a[1];
55     stack1[2]=a[2];
56     head=2;
57     for(i=3;i<n;i++)
58     {
59         while( head>=2 )
60         {
61             if( cross(stack1[head-1],stack1[head],a[i])< 0 )
62             head--;
63             else if( cross(stack1[head-1],stack1[head],a[i]) == 0 &&
64                     ( distance1(stack1[head-1],a[i]) > distance1(stack1[head-1],stack1[head]) ) )
65                         head--;
66             else break;
67         }
68         stack1[++head]=a[i];
69     }
70     tom(stack1,head);
71 }
72 int main()
73 {
74     int n,i;
75     while(scanf("%d",&n)>0)
76     {
77         for(i=0;i<n;i++)
78             scanf("%d%d",&a[i].x,&a[i].y);
79         Graham(n);
80     }
81     return 0;
82 }

关键是没有用到旋转卡壳算法。待续。

/**

由于程序在cmp()中，当发生多个点一起时，按距离小的排序。
这样的话，就会使得距离大的在最后面。根据代码可知
for(i=3;i<n;i++)
{
while( head>=2 && cross(stack1[head-1],stack1[head],a[i])<= 0) head--;
stack1[++head]=a[i];
}
这样的话，就不会丢失我们需要的那个点。

旋转卡壳算法，head+1传参。很明显，和求凸包的时候是一致的。
因为要对第head个点进行判断的时候，必须用到第0个点。

**/

 1 /*旋转卡壳算法*/
 2 #include<iostream>
 3 #include<stdio.h>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<algorithm>
 8 using namespace std;
 9 
10 struct node
11 {
12    int x,y;
13 };
14 node a[50002],stack1[50002];
15 int dis(node n1,node n2)
16 {
17     return  (n1.x-n2.x)*(n1.x-n2.x) + (n1.y-n2.y)*(n1.y-n2.y);
18 }
19 double cross(node a,node n1,node n2)
20 {
21     return (n1.x-a.x)*(n2.y-a.y) - (n1.y-a.y)*(n2.x-a.x);
22 }
23 bool cmp(node n1,node n2)
24 {
25     double k = cross(a[0],n1,n2);
26     if( k>0) return true;
27     else if( k==0 && dis(a[0],n1)<dis(a[0],n2))
28         return true;
29     else return false;
30 }
31 void tom(node *ch,int n)// 旋转卡壳算法。
32 {
33     int ans=0,p,q=1;
34     ch[n]=ch[0];//这个点的增加，是为了能使得最后一个点能被证实是正确的。
35     for(p=0;p<n;p++)
36     {
37         while( cross(ch[p+1],ch[q+1],ch[p]) > cross(ch[p+1],ch[q],ch[p]))
38             q=(q+1)%n;
39         ans=max(ans,max(dis(ch[p],ch[q]),dis(ch[p+1],ch[q+1])));
40     }
41     printf("%d
",ans);
42 }
43 void Graham(int n)
44 {
45     int i,head;
46     for(i=1;i<n;i++)
47         if(a[i].x<a[0].x ||(a[i].x==a[0].x&&a[i].y<a[0].y ) )
48             swap(a[0],a[i]);
49     sort(a+1,a+n,cmp);
50     a[n]=a[0];
51     stack1[0]=a[0];
52     stack1[1]=a[1];
53     stack1[2]=a[2];
54     head=2;
55     for(i=3;i<n;i++)
56     {
57         while( head>=2  && cross(stack1[head-1],stack1[head],a[i])<= 0) head--;
58         stack1[++head]=a[i];
59     }
60     tom(stack1,head+1);
61 }
62 int main()
63 {
64     int n,i;
65     while(scanf("%d",&n)>0)
66     {
67         for(i=0;i<n;i++)
68             scanf("%d%d",&a[i].x,&a[i].y);
69         Graham(n);
70     }
71     return 0;
72 }