백준1077 넓이

작성일 | In

문제 링크

  • http://icpc.me/1077

시간복잡도

  • $O(NM)$

풀이

두 다각형이 겹치지 않은 경우, 한 다각형이 다른 다각형을 완전히 포함하는 경우를 미리 예외처리합시다. 어떤 점이 볼록 다각형 $H$ 안에 있는지 판별하는 것은 $O(\log \vert H \vert)$ 시간에 할 수 있으므로 이 과정을 선형 로그 시간에 처리할 수 있지만, 굳이 그렇게 하지 않아도 됩니다.

만약 두 볼록다각형이 겹친다면, 교점은 정확히 두 개 존재합니다. 두 다각형의 변을 모두 보면서 겹치는 변이 있다면 교점을 구하고, 꼭짓점을 모두 보면서 교집합의 꼭짓점도 구합시다. 꼭짓점들을 모두 구했다면 다각형의 넓이를 계산하는 것은 신발끈 공식을 이용해서 쉽게 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using ld = long double;
using Point = pair<ld, ld>;
constexpr ld EPS = 1e-10;
Point operator + (const Point &a, const Point &b){ return { a.x + b.x, a.y + b.y }; }
Point operator - (const Point &a, const Point &b){ return { a.x - b.x, a.y - b.y }; }
ld    operator * (const Point &a, const Point &b){ return a.x*a.x + a.y*a.y; }
ld    operator / (const Point &a, const Point &b){ return a.x*b.y - b.x*a.y; }
Point operator * (const Point &a, ld b){ return { a.x * b, a.y * b }; }
Point operator / (const Point &a, ld b){ return { a.x / b, a.y / b }; }
istream& operator >> (istream &in, Point &t){ in >> t.x >> t.y; return in; }

ld CCW(const Point &p1, const Point &p2, const Point &p3){
    auto res = (p2 - p1) / (p3 - p2);
    return (res > 0) - (res < 0);
}
ld D(const Point &p1, const Point &p2){
    return (p1 - p2) * (p1 - p2);
}

bool Cross(Point s1, Point e1, Point s2, Point e2){
    auto cw1 = CCW(s1, e1, s2) * CCW(s1, e1, e2);
    auto cw2 = CCW(s2, e2, s1) * CCW(s2, e2, e1);
    if(cw1 == 0 && cw2 == 0){
        if(s1 > e1) swap(s1, e1);
        if(s2 > e2) swap(s2, e2);
        return !(e1 < s2 || e2 < s1);
    }
    return cw1 <= 0 && cw2 <= 0;
}

bool Cross(Point s1, Point e1, Point s2, Point e2, Point &res){
    if(!Cross(s1, e1, s2, e2)) return false;
    ld det = (e1 - s1) / (e2 - s2);
    if(abs(det) < EPS) return false;
    res = s1 + (e1 - s1) * ((s2 - s1) / (e2 - s2) / det);
    return true;
}

struct ConvexHull{
    vector<Point> pts;
    void build(vector<Point> a){
        swap(a[0], *min_element(all(a)));
        sort(a.begin()+1, a.end(), [&](const Point &s, const Point &e){
            ld cw = CCW(a[0], s, e);
            if(cw != 0) return cw > 0;
            return D(a[0], s) < D(a[0], e);
        });
        pts.clear();
        for(auto i : a){
            while(pts.size() >= 2 && CCW(pts[pts.size()-2], pts.back(), i) <= 0) pts.pop_back();
            pts.push_back(i);
        }
        assert(pts.size() >= 3);
    }
    bool contain(const Point &p) const {
        int i = lower_bound(pts.begin()+1, pts.end(), p, [&](const Point &a, const Point &b){
            ld cw = CCW(pts[0], a, b);
            if(cw) return cw > 0;
            return D(pts[0], a) < D(pts[0], b);
        }) - pts.begin();
        if(i == pts.size()) return 0;
        if(i == 1) return CCW(pts[0], p, pts[1]) == 0 && pts[0] <= p && p <= pts[1];
        int t1 = CCW(pts[0], p, pts[i]) * CCW(pts[0], p, pts[i-1]);
        int t2 = CCW(pts[i], pts[i-1], pts[0]) * CCW(pts[i], pts[i-1], p);
        if(t1 == -1 && t2 == -1) return 0;
        return CCW(pts[0], p, pts[i-1]) != 0;
    }
    bool contain(const ConvexHull &h) const {
        for(const auto &i : h.pts) if(!contain(i)) return false;
        return true;
    }
    ld area() const {
        ld ret = 0;
        for(int i=0; i<pts.size(); i++){
            int j = i + 1; if(j == pts.size()) j = 0;
            ret += pts[i].x * pts[j].y;
            ret -= pts[j].x * pts[i].y;
        }
        return abs(ret) / 2.0L;
    }
    vector<pair<Point, Point>> edges() const {
        vector<pair<Point, Point>> ret;
        for(int i=0; i+1<pts.size(); i++) ret.emplace_back(pts[i], pts[i+1]);
        if(pts.size() > 1) ret.emplace_back(pts.back(), pts[0]);
        return move(ret);
    }
} H1, H2, H;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<Point> P1(N), P2(M);
    for(auto &i : P1) cin >> i;
    for(auto &i : P2) cin >> i;
    H1.build(P1); H2.build(P2);

    if(H1.contain(H2)){ cout << fixed << setprecision(20) << H2.area(); return 0; }
    if(H2.contain(H1)){ cout << fixed << setprecision(20) << H1.area(); return 0; }

    auto E1 = H1.edges(), E2 = H2.edges();
    vector<Point> P;
    for(auto i : E1){
        for(auto j : E2){
            Point p;
            if(!Cross(i.x, i.y, j.x, j.y, p)) continue;
            P.push_back(p);
        }
    }
    for(auto i : H1.pts) if(H2.contain(i)) P.push_back(i);
    for(auto i : H2.pts) if(H1.contain(i)) P.push_back(i);
    if(P.empty()){ cout << 0; return 0; }
    H.build(P);
    cout << fixed << setprecision(20) << H.area();
}