网站模版如何使用,网站开发字体,手机如何自动备份wordpress,商城网站免费建设G - 飞花的传送门飞花壕最近手头比较宽裕#xff0c;所以想买两个传送门来代步#xff08;夏天太热#xff0c;实在是懒得走路#xff09;。平面上有N个传送门#xff0c;飞花壕想要挑两个距离最远的传送门带回家#xff08;距离为欧几里得距离#xff0c;即两点之间直线… G - 飞花的传送门 飞花壕最近手头比较宽裕所以想买两个传送门来代步夏天太热实在是懒得走路。平面上有N个传送门飞花壕想要挑两个距离最远的传送门带回家距离为欧几里得距离即两点之间直线距离。 请你帮他算一算他所挑选的最远的两个传送门有多远。 Input 多组输入。 对于每组输入第一行输入一个整数N2 N 50000接下来从第2行到第N1行每行两个整数XiYi代表第i个传送门的坐标-1000000 Xi , Yi 1000000。 数据为随机生成。 Output 输出一个整数代表飞花壕要挑选的两个传送门的距离的平方。 Sample Input 4
0 0
0 1
1 1
1 0 Sample Output 2 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #includestack6 #include math.h7 #include stdio.h8 #include algorithm9 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.xb.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 10000005;
48 for(i0;in;i)
49 {
50 scanf(%lld%lld,P[i].x,P[i].y);
51 if(P[i].yyy)
52 {
53 yy P[i].y;
54 xx P[i].x;
55 j i;
56 }
57 }
58 P[j] P[0];
59 sort(P1,Pn,cmp);
60 S[0].x xx;
61 S[0].y yy;
62 S[1] P[1];
63 for(i 2;in;)
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;itop;i)
70 for( j i1;jtop;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 } 转载于:https://www.cnblogs.com/LGJC1314/p/6843638.html
