LK的旅行（简单凸包应用）

 

描述

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

思路：emmm，时间要求2s，挺长，枚举暴一暴吧。呵呵，难度5暴就能过吗，太天真了，居然还有侥幸心理。这道题需要明确一点，n个点求最大2点距离，那么这2个点只可能在凸点上，然后取出凸点再枚举各凸点距离取最大即可。

 

 

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
}a[10005],s[10005];
int cmp(node a,node b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);  
}
double fun2(node a,node b)//两点之间距离平方公式
{
    return (pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
int fun(node a,node b,node c)//叉乘
{
    if((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)>0)
    return 1;
    return 0;
}
int main()
{
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        scanf("%d %d",&a[i].x,&a[i].y);
        sort(a,a+m,cmp);
        double sum;
        int top=0;
        for(int i=0;i<m;i++)
        {
            while(top>=2&&fun(s[top-2],s[top-1],a[i])!=1)
            top--;
            s[top++]=a[i];
        }
        int t=top-1;
        for(int i=m-1;i>=0;i--)
        {
            while(top>=t+2&&fun(s[top-2],s[top-1],a[i])!=1)
            top--;
            s[top++]=a[i];
        }
        --top;
        sum=-1;
        for(int i=0;i<top;i++)
        {
            for(int j=i;j<top;j++)
            {
                double  l=fun2(s[i],s[j]);
                sum=max(sum,l);
            }
        }
        printf("%.0lf\n",sum);
    }
    return 0;
}