LK的旅行
时间限制：2000 ms | 内存限制：65535 KB
难度：5
- 描述
-
LK最近要去某几个地方旅行，她从地图上计划了几个点，并且用笔点了出来，准备在五一假期去这几个城市旅行。现在希望你找出她点的所有的点中距离最远的两个点的距离是多少。各个景点可以认为是在一个平面上。
- 输入
- 第一行有一个整数0<n<10表示测试数据的组数随后的n组数据中，第一行有一个整数3<m<100000表示有m个旅游景点。随后的m行每行有两个整数，分别表示每一个点的x和y。景点坐标中可能有重复的，0<=x，y<=10000）
- 输出
- 每组数据输出距离最远的点对的距离的平方.
- 样例输入
-
1
4
0 0
1 1
0 1
1 0 - 样例输出
-
2
代码：#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int num=;
int N;
struct Point
{
int x;
int y;
}points[num],output[num];
inline int ccw(Point p1,Point p2,Point p3) //交叉乘积
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
inline int dis(Point p1,Point p2) //距离
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int cmp(const void *po1,const void *po2) //排序用的比较函数
{
Point *p1=(Point *)po1;
Point *p2=(Point *)po2;
int temp=ccw(points[],*p1,*p2); //先判断方向
if(temp>)
{
return -;
}
else if(temp<)
{
return ;
}
else
{
return dis(*p1,points[])-dis(*p2,points[]); //共线时按距离从大到校排序
}
} int maxDist( )
{
int min_index=;
for(int i=;i<N;i++)
{
if(points[i].x<points[min_index].x)
min_index=i;
else if(points[i].x<points[min_index].x&&points[i].y<points[min_index].y)
min_index=i;
}
swap(points[],points[min_index]); //找到y坐标最小的点，并交换到第一个位置
qsort(points+,N-,sizeof(Point),cmp); //排序
/* for(int i=0;i<N;i++)
{
printf("%d %d\n",points[i].x,points[i].y); }*/
output[]=points[];
output[]=points[];
int top=;
i=;
while(i<N)
{
// printf("%d %d\n",points[i].x,points[i].y); int temp=ccw(output[top-],output[top],points[i]);
if(temp>=)
{
output[++top]=points[i];
i++;
}
/*else if(temp==0)
{
output[top]=points[i];
i++;
}*/
else
{
top--;
}
}
int maxD=;
for( i=;i<=top;i++) //计算边界点之间的距离
{
// printf("%d %d\n",output[i].x,output[i].y);
for(int j=i+;j<=top;j++)
{
int temp=dis(output[i],output[j]);
if(temp>maxD)
maxD=temp;
}
}
printf("%d\n",maxD);
return maxD; } int main()
{
int T;
scanf("%d",&T);
while(T--) //输入
{
scanf("%d",&N);
for(int i=;i<N;i++)
{
scanf("%d %d",&points[i].x,&points[i].y);
//printf("%d %d\n",points[i].x,points[i].y);
}
maxDist();
}
return ;
}