G -?飛花的傳送門

飛花壕最近手頭比較寬裕，所以想買兩個傳送門來代步（夏天太熱，實在是懶得走路）。平面上有N個傳送門，飛花壕想要挑兩個距離最遠(yuǎn)的傳送門帶回家（距離為歐幾里得距離，即兩點之間直線距離）。

請你幫他算一算他所挑選的最遠(yuǎn)的兩個傳送門有多遠(yuǎn)。

Input

?

多組輸入。

對于每組輸入，第一行輸入一個整數(shù)N（2 <= N<= 50000），接下來從第2行到第N+1行，每行兩個整數(shù)（X_i，Y_i），代表第i個傳送門的坐標(biāo)（-1000000 <= X_i?, Y_i?<= 1000000）。

數(shù)據(jù)為隨機生成。

Output

?

輸出一個整數(shù)，代表飛花壕要挑選的兩個傳送門的距離的平方。

Sample Input

4 0 0 0 1 1 1 1 0

Sample Output

2 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<stack> 6 #include <math.h> 7 #include <stdio.h> 8 #include <algorithm> 9 using namespace std; 10 struct point 11 { 12 long long x; 13 long long y; 14 } P[50005],S[50005]; 15 16 long long xx; 17 long long yy; 18 19 bool cmp(struct point a,struct point b) 20 { 21 if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx)) 22 return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx)); 23 return a.x<b.x; 24 } 25 26 long long CJ(long long x1,long long y1,long long x2,long long y2) 27 { 28 return (x1*y2-x2*y1); 29 } 30 31 long long Compare(struct point a,struct point b,struct point c) 32 { 33 return CJ((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y)); 34 } 35 36 long long Dis(struct point a,struct point b) 37 { 38 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); 39 } 40 41 int main() 42 { 43 int n,i,j; 44 while(~scanf("%d",&n)) 45 { 46 int top = 1; 47 yy = 1000000+5; 48 for(i=0;i<n;i++) 49 { 50 scanf("%lld%lld",&P[i].x,&P[i].y); 51 if(P[i].y<yy) 52 { 53 yy = P[i].y; 54 xx = P[i].x; 55 j = i; 56 } 57 } 58 P[j] = P[0]; 59 sort(P+1,P+n,cmp); 60 S[0].x = xx; 61 S[0].y = yy; 62 S[1] = P[1]; 63 for(i = 2;i<n;) 64 { 65 if(top&&(Compare(S[top-1],S[top],P[i])<0)) top--; 66 else S[++top] = P[i++]; 67 } 68 long long max1 = -1; 69 for(i = 0;i<=top;i++) 70 for( j = i+1;j<=top;j++) 71 if(Dis(S[i],S[j])>max1) 72 max1 = Dis(S[i],S[j]); 73 printf("%lld\n",max1); 74 } 75 return 0; 76 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LGJC1314/p/6843638.html

總結(jié)

以上是生活随笔為你收集整理的山东理工大学第七届ACM校赛-G 飞花的传送门的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。