POJ（2187）用凸包求最远点对

Beauty Contest

题目描述：输入n对整数点，求最距离远的点对，输出他们距离的平方和

算法：拿到这个题，最朴素的想法就是用2层循环遍历所有的点对，但这样可能会超时。由于距离最远的点对必定在点集的凸包的顶点上，所以只用遍历凸包上的点对就行。这样就把可能存在的大量的点给排除。哈哈~~~还是凸包。

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
struct Node
{
    int x,y;
    Node operator-(Node &node)
    {
        Node new_node;
        new_node.x=x-node.x;
        new_node.y=y-node.y;
        return new_node;
    }
};
vector<Node> p,s; //p存放所有顶点，s存放凸包顶点,s模拟栈
const double eps=10e-6;
int squared_distance(Node &a,Node &b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

double cross(Node vec1,Node vec2)
{
    return (double)(vec1.x*vec2.y-vec1.y*vec2.x);
}
bool cmp(Node &a,Node &b)
{
    Node vec1=a-p[0];
    Node vec2=b-p[0];
    double temp=cross(vec1,vec2);
    if(temp>eps)
        return true;
    else if(temp<eps)
        return false;
    else
    {
        if(squared_distance(a,p[0])<squared_distance(b,p[0]))
            return true;
        else
            return false;
    }
}
void swap(Node &a,Node &b)
{
    Node temp;
    temp=a;
    a=b;
    b=temp;
}
int lowleft(vector<Node> &p)
{
    int len=p.size();
    int min_x=p[0].x,min_y=p[0].y;
    int k=0;
    for(int i=0;i<len;i++)
    {
        if(p[i].y<min_y)
        {
            min_x=p[i].x;
            min_y=p[i].y;
            k=i;
        }
        else if(p[i].y==min_y&&p[i].x<min_x)
        {
            min_x=p[i].x;
            k=i;
        }
    }
    return k;
}
void graham(vector<Node> &p)
{
    int k=lowleft(p);
    swap(p[0],p[k]);
    sort(p.begin()+1,p.end(),cmp);
    p.push_back(p[0]);

    s.push_back(p[0]);
    s.push_back(p[1]);
    
    int top=1;
    int len=p.size();
    for(int i=2;i<len;i++)
    {
        while(top>=1&&cross(s[top]-s[top-1],p[i]-s[top])<0)
        {
            s.pop_back();
            top--;
        }
        s.push_back(p[i]);
        top++;
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        Node temp;
        p.clear();
        s.clear();
        for(int i=0;i<n;i++)
        {
            cin>>temp.x>>temp.y;
            p.push_back(temp);
        }
        graham(p);
        int max=0;
        int len=s.size()-1;//p的最后一个元素的值是p[0]遍历
        for(int i=0;i<len-1;i++)
        {
            for(int j=i+1;j<len;j++)
            {
                int d=squared_distance(s[i],s[j]);
                if(d>max)
                    max=d;
            }
        }
        cout<<max<<endl;
    }
    return 0;
}

View Code