1 #include<iostream>
2using namespace std;
3struct Node
4   {
5 int x,y;
6 }node[50010];
7int N;
8Node temp;
9int Dist(Node a,Node b)
10{
11 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
12}
13int Mult(Node a,Node b,Node c)
14{
15 return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
16}
17
18
19int cmp(const void *a,const void *b)
20{
21 Node *c=(Node *)a;
22 Node *d=(Node *)b;
23 int m=Mult(node[0],*c,*d);
24 if(m==0)
25 return Dist(*c,node[0])-Dist(*d,node[0]);
26 return -m;
27
28}
29
30int main()
31{
32 int i,j,k,m;
33 cin>>N;
34 for(i=0;i<N;i++)
35  {
36 cin>>node[i].x>>node[i].y;
37 if(node[i].y<node[0].y || (node[i].y==node[0].y && node[i].x>node[0].x))
38 {
39 temp=node[i];
40 node[i]=node[0];
41 node[0]=temp;
42 }
43 }
44 qsort(node+1,N-1,sizeof(node[0]),cmp);
45 /**//*
46 for(i=0;i<N;i++)
47 cout<<node[i].x<<' '<<node[i].y<<endl;
48 cout<<endl<<endl;
49 */
50 int cnt=1;
51 int top=1;
52 for(i=2;i<N;i++)
53 {
54 while(top>=1 && (Mult(node[top-1],node[top],node[i]))<=0)
55 top--;
56 node[++top]=node[i];
57 }
58// for(i=0;i<N;i++)
59// cout<<node[i].x<<' '<<node[i].y<<endl;
60// cout<<endl<<endl;
61 int res=0;
62 for(i=0;i<top;i++)
63 {
64 for(j=i+1;j<=top;j++)
65 {
66 k=Dist(node[i],node[j]);
67 // cout<<i<<" "<<j<<" "<<k<<endl;
68 if(res<k)
69 res=k;
70 }
71 }
72// cout<<top<<endl;
73 cout<<res<<endl;
74 return 0;
75}
76
|