這個(gè)題意思很清楚，求50000個(gè)點(diǎn)中距離最大的兩個(gè)點(diǎn)，并輸出最大距離，普通的o(n^2)是過不了的，正確的做法應(yīng)該是利用凸包graham-scan(o(nlogn))掃描法縮小點(diǎn)集，然后用一個(gè)旋轉(zhuǎn)卡殼的的算法(o(n))求出凸多邊形的直徑，但是當(dāng)我在寫旋轉(zhuǎn)卡殼的時(shí)候wa了，我瘋了，換了一個(gè)普通的二重循環(huán)居然過了，數(shù)據(jù)不強(qiáng)，要是那50000個(gè)點(diǎn)都為凸包的頂點(diǎn)就慘了。
1
/**//*
2
Name: pku2187
3 Copyright: ccnu
4 Author: Torres
5 Date: 11-08-08 15:08
6 Description: 利用凸包縮小點(diǎn)集求最大距離
7
*/
8
#include<iostream>
9#include<cmath>
10#include<algorithm>
11using namespace std;
12const double pi=acos(-1.0);
13typedef struct point
{
14 double x,y;
15 point(double x=0,double y=0)
16
{this->x=x;this->y=y;}
17}point;
18int n;
19point p[50005],ch[50005];
20int top;
21
22//p0p1 crossmul p0p2
23double cross(point p0,point p1,point p2)
24{return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}
25
26double dist(point a,point b)
27{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
28
29bool cmp(point a,point b)
30{
31 double re=cross(p[0],a,b);
32 if(re>0)return true;
33 else if(!re&&dist(p[0],a)>dist(p[0],b))
34 return true;
35 else return false;
36}
37
38void graham(point a[])
39{
40 int i,j=0;
41 for(i=1;i<n;i++)
42 if(a[i].y<a[j].y||a[i].y==a[j].y&&a[i].x<a[j].x)j=i;
43 swap(a[0],a[j]);//找出左下點(diǎn)
44 sort(a+1,a+n,cmp);
45 ch[0]=a[0];ch[1]=a[1];ch[2]=a[2];top=2;
46 for(i=3;i<n;i++){
47 while(cross(ch[top-1],a[i],ch[top])>=0)
48 {
49 top--;
50 if(top==1)break;
51
}
52 ch[++top]=a[i];//試探
53 }
54}
55int main()
56{
57 int i,j;
58 int len=0;
59 scanf("%d",&n);
60 for(i=0;i<n;i++)
61 scanf("%lf%lf",&p[i].x,&p[i].y);
62 graham(p);
63 for(i=0;i<=top;i++)
64 for(j=0;j<=top;j++){
65 double temp=dist(ch[i],ch[j]);
66 if(len<temp)len=(int)temp;
67 }
68 printf("%d\n",len);
69 return 0;
70}
71
72