POJ 2187 Beauty Contest（计算几何凸包）

Beauty Contest

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 19373		Accepted: 5850

Description

Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates.

Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.

Input

* Line 1: A single integer, N

* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm

Output

* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.

Sample Input

0 0

0 1

1 1

1 0

Sample Output

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)

Source

USACO 2003 Fall

解题报告：就是求点之间的做大距离的平方，利用Graham()算法选取点构成凸包，则两点之间的最大距离一定在凸包的顶点上，再遍历一次求两点间的距离即可！

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAX = 50010;
int n, top;//top用来记录形成凸包点的数目
double ans;
struct Point
{
    double x;
    double y;
}p[MAX];//存储点的坐标
int convex[MAX];//记录形成凸包的点的次序按逆时针
double Max(double a, double b)
{
    return a > b ? a : b;
}
int cmp(Point a, Point b)//先按y从小到大排序，若y相等，再按x从小到大排序
{
    if (a.y == b.y) return a.x < b.x;
    else return a.y < b.y;
}
double Dis(int i, int j)//计算两点间的距离的平方
{
    return ((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
}
double Multi(Point p1, Point p2, Point p3)//用叉乘判断点的位置
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
void Graham()//选取点形成凸包（不包含边上的点）选取的点数是最小的，按逆时针选择的
{
    int i, count;
    top = 1;
    sort(p, p + n, cmp);
    for (i = 0; i < 3; ++i)
    {
        convex[i] = i;
    }
    for (i = 2; i < n; ++i)
    {
        while (top && Multi(p[i], p[convex[top]], p[convex[top - 1]]) >= 0)
        {
            top --;
        }
        convex[++ top] = i;
    }
    count = top;
    convex[++ top] = n - 2;
    for (i = n - 3; i >= 0; --i)
    {
        while (top != count && Multi(p[i], p[convex[top]], p[convex[top - 1]]) >= 0)
        {
            top --;
        }
        convex[++ top] = i;
    }
}
int main()
{
    int i, j;
    double dis;
    while (scanf("%d", &n) != EOF)
    {
        for (i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        Graham();
        ans = 0;//初始化
        for (i = 0; i < top; ++i)
        {
            for (j = 0; j < i; ++j)
            {
                dis = Dis(convex[i], convex[j]);
                ans = Max(ans, dis);
            }
        }
        printf("%.0lf\n", ans);
    }
    return 0;
}

POJ 2187 Beauty Contest（计算几何 凸包）

POJ 2187 Beauty Contest（计算几何凸包）