SDUT 3271 飞花的传送门(凸包)解题报告

2016-08-23 1,384 次浏览 解题报告

题面

飞花的传送门
Time Limit: 1000ms Memory limit: 65536K

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

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

输入
多组输入。

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

数据为随机生成。

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

示例输入
4
0 0
0 1
1 1
1 0

示例输出
2

提示

来源
GLSilence

所需基础

计算几何 - 凸包

解题思路

这题直接拿 POJ 2187 原题汉化了就搬过来当校赛题了,示例都一模一样,唯一的不同就是数据范围大了一些,需要用 long long,也是醉了。此题是标准的凸包裸题(对凸包的代码实现理解有困难的,可以参考我的这篇博客),和 POJ 2187 一样,求出凸包后枚举凸包上所有的点,两两构成线段,找出最大长度即可,不需要使用旋转卡壳。我这里用的是水平序的 Graham's Scan 算法,写起来会比极角序简单很多,而且不用纠结共线问题。

参考代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct point {
    long long x;
    long long y;
    point operator - (const point &p) const {
        point ret;
        ret.x = x - p.x;
        ret.y = y - p.y;
        return ret;
    }
} p[50000];

int n;

bool cmp(point a, point b) {    //水平序
    if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

long long Det(long long x1, long long y1, long long x2, long long y2) {
    return x1*y2 - x2*y1;
}

long long Cross(point a, point b, point p) {
    return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}

long long CalculateDistance(point a, point b) {
    point p = a - b;

    return p.x*p.x + p.y*p.y;
}

long long GrahamScan() {
    point res[50000];
    int top = 0;
    for(int i=0; i<n; ++i) {    //扫描右链
        while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    int tmp = top;
    for(int i=n-2; i>=0; --i) {    //扫描左链
        while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    long long ans = 0;
    for(int i=0; i<top; ++i) {    //枚举找最大长度
        for(int j=i+1; j<top; ++j) {
            ans = max(ans, CalculateDistance(res[i], res[j]));
        }
    }

    return ans;
}

int main(int argc, char const *argv[]) {
    while(~ scanf("%d", &n)) {
        for(int i=0; i<n; ++i) {
            scanf("%lld %lld", &p[i].x, &p[i].y);
        }
        sort(p, p+n, cmp);
        printf("%lld\n", GrahamScan());
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/08/23/sdut-3271.dream

还不快抢沙发

添加新评论