首页技术正文

山东理工大学第七届ACM校赛-G 飞花的传送门

程序员俊娜技术 2022年11月12日

0 收藏 958 点赞 4,891 浏览 1343 个字

G – 飞花的传送门

飞花壕最近手头比较宽裕，所以想买两个传送门来代步（夏天太热，实在是懒得走路）。平面上有N个传送门，飞花壕想要挑两个距离最远的传送门带回家（距离为欧几里得距离，即两点之间直线距离）。

请你帮他算一算他所挑选的最远的两个传送门有多远。

Input

多组输入。

对于每组输入，第一行输入一个整数N（2 <= N<= 50000），接下来从第2行到第N+1行，每行两个整数（X_i，Y_i），代表第i个传送门的坐标（-1000000 <= X_i, Y_i<= 1000000）。

数据为随机生成。

Output

输出一个整数，代表飞花壕要挑选的两个传送门的距离的平方。

Sample Input

Sample Output

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<stack>
 #include <math.h>
 #include <stdio.h>
 #include <algorithm>
 using namespace std;
 struct point
 {
     long long  x;
     long long  y;
 } P[],S[]; long long  xx;
 long long  yy; bool cmp(struct point a,struct point b)
 {
     if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
         return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
     return a.x<b.x;
 } long long  CJ(long long  x1,long long  y1,long long  x2,long long  y2)
 {
     return (x1*y2-x2*y1);
 } long long Compare(struct point a,struct point b,struct point c)
 {
     return CJ((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
 } long long Dis(struct point a,struct point b)
 {
     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
 } int main()
 {
     int n,i,j;
     while(~scanf("%d",&n))
     {
         int top = ;
         yy = +;
         for(i=;i<n;i++)
         {
             scanf("%lld%lld",&P[i].x,&P[i].y);
             if(P[i].y<yy)
             {
                 yy = P[i].y;
                 xx = P[i].x;
                 j = i;
             }
         }
         P[j] = P[];
         sort(P+,P+n,cmp);
         S[].x = xx;
         S[].y = yy;
         S[] = P[];
         for(i = ;i<n;)
         {
             if(top&&(Compare(S[top-],S[top],P[i])<)) top--;
             else S[++top] = P[i++];
         }
         long long max1 = -;
         for(i = ;i<=top;i++)
             for( j = i+;j<=top;j++)
                 if(Dis(S[i],S[j])>max1)
                     max1 = Dis(S[i],S[j]);
         printf("%lld\n",max1);
     }
     return ;
 }