백준2080 겹치는 선분

작성일 | In

문제 링크

  • http://icpc.me/2080

사용 알고리즘

  • CCW

풀이

선분/직선은 $y = ax + b$로 표현할 수 있고, 두 선분의 $a, b$가 모두 같은 경우에만 두 직선이 겹칠 수 있습니다.
주어진 선분을 $a, b$ 값 별로 나눈 다음, 각각에 대해 독립적으로 문제를 해결해도 충분합니다.
간단한 스위핑을 통해 문제를 해결할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;

struct Line{
    ll x, y, xx, yy;
    Line() = default;
    Line(ll x, ll y, ll xx, ll yy) : x(x), y(y), xx(xx), yy(yy) {}
    bool operator < (const Line &t) const {
        if(tie(x, y) != tie(t.x, t.y)) return tie(x, y) < tie(t.x, t.y);
        return tie(xx, yy) > tie(t.xx, t.yy);
    }
};

struct LineCompare{
    ll a1, a2, b1, b2; // y = (a1/a2)x + (b1/b2)
    int flag; // 0: normal, 1: dx=0, 2: dy=0, 3: dx=dy=0
    LineCompare() = default;
    LineCompare(ll a1, ll a2, ll b1, ll b2, int flag) : a1(a1), a2(a2), b1(b1), b2(b2), flag(flag) {}
    bool operator < (const LineCompare &t) const {
        return tie(a1, a2, b1, b2, flag) < tie(t.a1, t.a2, t.b1, t.b2, t.flag);
    }
};

struct Event{
    ll x, y; int v;
    Event() = default;
    Event(ll x, ll y, int v) : x(x), y(y), v(v) {}
    bool operator < (const Event &t) const {
        return tie(x, y, v) < tie(t.x, t.y, t.v);
    }
};

LineCompare Get(const Line &line){
    ll dx = line.xx - line.x, dy = line.yy - line.y;
    if(dx == 0 && dy == 0) return {0, 0, 0, 0, 3};
    if(dy == 0) return {line.y, 1, 0, 0, 2};
    if(dx == 0) return {line.x, 1, 0, 0, 1};

    ll a1 = dy, a2 = dx;
    ll b1 = line.xx * line.y - line.x * line.yy, b2 = dx;

    ll ga = __gcd(a1, a2), gb = __gcd(b1, b2);
    a1 /= ga; a2 /= ga; b1 /= gb; b2 /= gb;
    return {a1, a2, b1, b2, 0};
}

int N;
Line A[101010];
map<LineCompare, vector<Line>> mp;
ll ans;

void Solve(const vector<Line> &v, const LineCompare &com){
    bool useY = com.flag == 2;
    vector<Event> event;
    for(const auto &i : v){
        event.emplace_back(i.x, i.y, 1);
        event.emplace_back(i.xx, i.yy, -1);
    }
    sort(all(event));
    ll acc = 0;
    for(const auto &i : event){
        if(i.v == 1) ans += acc;
        acc += i.v;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> A[i].x >> A[i].y >> A[i].xx >> A[i].yy;
        if(tie(A[i].x, A[i].y) > tie(A[i].xx, A[i].yy)){
            swap(A[i].x, A[i].xx);
            swap(A[i].y, A[i].yy);
        }
        mp[Get(A[i])].push_back(A[i]);
    }

    for(const auto &v : mp) Solve(v.second, v.first);
    cout << ans;
}