1 //2187 Accepted 1600K 375MS G++ 4578B --gramcmp
2 //2187 Accepted 1600K 438MS G++ 4590B --gramcmp1
3 //利用凸包來求最遠點對
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <ctype.h>
9 #include <math.h>
10 #include <iostream>
11 using namespace std ;
12 #define unllong unsigned long long
13 #define unint unsigned int
14 #define printline printf( "\n" )
15 typedef long long llong ;
16
17 #define zero(x) (((x)>0?(x):-(x))<eps)
18
19 const int Base=1000000000;//高精度
20 const int Capacity=100;//高精度
21 const double PI = 2.0*acos( 0.0 ) ;
22 const double eps = 1e-8 ;
23 const int INF = 1000000 ;
24
25 const int size = 100010 ;
26
27 struct POINT
28 {
29 double x ;
30 double y ;
31 double k ;
32 };
33 struct POINT point[size] ;
34
35 int stack[size] ;
36 int top = 2 ;
37
38 int inn; int inr ;
39 double outarea ;
40 double outlen ;
41
42 double fdist( double x1, double y1, double x2, double y2 )
43 {
44 return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
45 }
46
47 void input()
48 {
49 int leftdown = 0 ;
50 for( int i=0; i<inn; i++ ) {
51 scanf( "%lf %lf", &point[i].x, &point[i].y ) ;
52 //if( miny>point[i].y || miny==point[i].y&&minx>point[i].x )
53 if( point[leftdown].y>point[i].y||zero(point[leftdown].y-point[i].y)&&point[leftdown].x>point[i].x )
54 leftdown = i ;//找到最左下的點
55 }
56 double temp ;
57 temp = point[0].x ; point[0].x = point[leftdown].x ; point[leftdown].x = temp ;
58 temp = point[0].y ; point[0].y = point[leftdown].y ; point[leftdown].y = temp ;
59 for( int i=1; i<inn; i++ ) {
60 point[i].k = atan2( point[i].y-point[0].y, point[i].x-point[0].x ) ;
61 }//以點(minx, miny)計算極角
62 }
63
64 double xmult( POINT &p1, POINT &p2, POINT &p0 )
65 {//計算叉乘--線段旋轉方向和對應的四邊形的面積--返回(p1-p0)*(p2-p0)叉積
66 //if叉積為正--p0p1在p0p2的順時針方向; if(x==0)共線
67
68 return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y) ;
69 }
70
71 int gramcmp1( const void *a, const void *b )
72 {
73 struct POINT *c = (struct POINT *)a ;
74 struct POINT *d = (struct POINT *)b ;
75
76 if( c->k - d->k > eps ) return 1 ;
77 else if( c->k - d->k < -1*eps ) return -1 ;
78 else//斜率相等距離近的點在先
79 return c->x - d->x > 0 ? 1 : -1 ;
80 }
81
82 int gramcmp( const void *a, const void *b )
83 {
84 struct POINT *c = (struct POINT *)a ;
85 struct POINT *d = (struct POINT *)b ;
86
87 double xmult_val = xmult( *c, *d, point[0] ) ;
88 if( xmult_val > eps ) return -1 ;
89 else if( xmult_val < -1*eps ) return 1 ;
90 else return c->x - d->x > 0 ? 1 : -1 ;
91 //else
92 //return fdist( c->x,c->y,point[0].x,point[0].y )>fdist(d->x,d->y,point[0].x,point[0].y)? -1:1 ;
93 }
94
95 void gramham()
96 {//凸包的點存在于stack[]中
97 qsort( point+1, inn-1, sizeof(point[1]), gramcmp1 ) ;//極坐標排序--注意只有(n-1)個點
98
99 //int stack[size] ; int top = 2 ;
100 stack[0] = 0 ; stack[1] = 1 ; stack[2] = 2 ; top = 2 ;
101
102 for( int i=3; i<inn; i++ )
103 {
104 while( top>=1&&xmult( point[i], point[stack[top]], point[stack[top-1]] )>=-1*eps )
105 top-- ;//順時針方向--刪除棧頂元素
106 stack[++top] = i ;//新元素入棧
107 }
108 /*
109 for( int i=0; i<=top; i++ )
110 {
111 //printf( "%lf===%lf\n",point[stack[i]].x, point[stack[i]].y ) ;
112 cout << point[stack[i]].x << "====" << point[stack[i]].y << endl ;
113 }
114 */
115 }
116
117 double flen_poly()
118 {//計算凸包的周長
119 double len = 0.0 ; double x1, x2, y1, y2 ;
120 for( int i=0; i<top; i++ ) {
121 x1 = point[stack[i+1]].x ; x2 = point[stack[i]].x ;
122 y1 = point[stack[i+1]].y ; y2 = point[stack[i]].y ;
123 len += fdist( x1, y1, x2, y2 ) ;
124 }
125 x1 = point[stack[0]].x ; x2 = point[stack[top]].x ;
126 y1 = point[stack[0]].y ; y2 = point[stack[top]].y ;
127 len += fdist( x1, y1, x2, y2 ) ;
128
129 return len ;
130 }
131
132 double farea_poly( int n, POINT poly[] )
133 {
134 double area = 0.0 ; double s1 = 0.0 , s2 = 0.0 ;
135 for( int i=0; i<n; i++ )
136 {
137 s1 += poly[stack[(i+1)%n]].y * poly[stack[i%n]].x ;
138 s2 += poly[stack[(i+1)%n]].y * poly[stack[(i+2)%n]].x ;
139 }
140
141 return fabs( s1 - s2 ) / 2 ;
142 }
143
144 int fdist2( double x1, double y1, double x2, double y2 )
145 {
146 return (int)( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
147 }
148
149 void find_maxlength()
150 {
151 int maxlen = -1 ; int curlen = 0 ;
152 double x1, x2, y1, y2 ;
153 for( int sn=0; sn<=top; sn++ )
154 {
155 x1 = point[stack[sn]].x, y1 = point[stack[sn]].y ;
156 for( int en=sn+1; en<=top; en++ )
157 {
158 x2 = point[stack[en]].x, y2 = point[stack[en]].y ;
159 curlen = fdist2( x1, y1, x2, y2 ) ;
160 if( maxlen < curlen ) maxlen = curlen ;
161 }
162 }
163
164 printf( "%d\n", maxlen ) ;
165 }
166
167 void process()
168 {
169 gramham() ;//保存好凸包的點在stack[]中
170
171 find_maxlength() ;
172 }
173
174 int main()
175 {
176 //freopen( "fc.in", "r", stdin ) ;
177 //freopen( "fc.out","w",stdout ) ;
178
179 //freopen( "in.txt", "r", stdin ) ;
180
181 //while( scanf( "%d %d", &inn, &inr ) != EOF )
182 scanf( "%d", &inn ) ;
183 {
184 input() ;
185
186 process() ;
187
188 //output() ;
189 }
190
191 return 0 ;
192 }