CodeForces 166B – Polygons [凸包]

Link

http://codeforces.com/problemset/problem/166/B

Mean

给两个多边形,保证第一个为凸多边形。多边形三点不共线。问你第二个多边形是否在第一个多边形内部,也即所有点都在第一个多边形内部。

Analysis

求第一个多边形的凸包和两个多边形公共凸包,判断两个凸包是否相同。注意求凸包时要把共线中的点都加上。同时要判断第二个多边形中的点不能和第一个中的点重合。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 150000;

struct Point {
    ll x, y;
    Point(ll x = 0, ll y = 0): x(x), y(y) {};
    Point operator - (const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    bool operator < (const Point &rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
    bool operator == (const Point &rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};
int N, M;
Point po[maxn];
Point ans1[maxn], ans2[maxn];

inline ll cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

void convexHull(int ed, Point ch[], int &m){
    sort(po, po + ed);
    m = 0;
    int n = unique(po, po + ed) - po;
    for(int i = 0; i < n; ++i){
        while(m >= 2 && cross(ch[m-1]-ch[m-2], po[i]-ch[m-2]) < 0) --m;
        ch[m++] = po[i];
    }
    int k = m;
    for(int i = n - 2; i >= 0; --i){
        while(m > k && cross(ch[m-1]-ch[m-2], po[i]-ch[m-2]) < 0) --m;
        ch[m++] = po[i];
    }
    if(n > 1) --m;
}

bool judge() {
    int sz1, sz2;
    convexHull(N, ans1, sz1);
    for(int i = N; i < N + M; ++i)
        if(binary_search(po, po + N, po[i]))
            return false;
    convexHull(N + M, ans2, sz2);
    if(sz1 != sz2)
        return false;
    sort(ans1, ans1 + sz1);
    sort(ans2, ans2 + sz2);
    for(int i = 0; i < sz1; ++i)
        if(!(ans1[i]==ans2[i]))
            return false;
    return true;
}

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; ++i)
        scanf("%I64d%I64d", &po[i].x, &po[i].y);
    scanf("%d", &M);
    for(int i = N; i < N + M; ++i)
        scanf("%I64d%I64d", &po[i].x, &po[i].y);
    puts(judge() ? "YES" : "NO");
    return 0;
}

欢迎留言