백준 25315번 - N수매화검법 문제의 해설입니다.

핵심 아이디어#

서로 교차하는 베기 A와 베기 B가 있을 때, 두 베기가 사라지려면 딱 2가지 경우이다.
$W_{A} \times (m+1) + W_{B} \times (m)$ 아니면 $W_{A} \times (m) + W_{B} \times (m+1)$이다.
결국 $W_{A}$ 가 더해지느냐, 아니면 $W_{B}$가 더해지느냐의 차이다. 따라서 무조건 적은 값이 더해지는 게 이득이라는 사실을 알 수 있다.

즉, 모든 두 베기의 교차마다 두 베기 중 작은 가중치를 더해주면 되고, 모든 베기의 가중치를 전부 더해주면 그것이 정답이다.

풀이#

모든 베기가 $N(\leq 2500)$ 이므로 $N^2$ 만에 모든 베기의 쌍에 대해서 교차하는 지의 여부와 교차한다면 두 베기 중 가중치가 작은 걸 더해준다. 그리고 모든 베기의 가중치를 전부 더해준다.

선분 교차 판정은 CCW를 기준으로 판단한다. (선분 교차 판정 참고)

코드#

cpp
1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define all1(v) (v).begin()+1, (v).end()
6#define For(i, a, b) for(int i=(a); i<(b); i++)
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
10#define ft first
11#define sd second
12
13using namespace std;
14using ll = long long;
15using lll = __int128_t;
16using ulll = __uint128_t;
17using ull = unsigned long long;
18using ld = long double;
19using pii = pair<int, int>;
20using pll = pair<ll, ll>;
21using ti3 = tuple<int, int, int>;
22using tl3 = tuple<ll, ll, ll>;
23
24template<typename T> using ve = vector<T>;
25template<typename T> using vve = vector<vector<T>>;
26
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
29
30const int INF = 987654321;
31const int INF0 = numeric_limits<int>::max();
32const ll LNF = 987654321987654321;
33const ll LNF0 = numeric_limits<ll>::max();
34
35struct Point {
36    ll x, y;
37
38    Point() {}
39    Point(ll _x, ll _y) : x(_x), y(_y) {}
40    ll cross(Point other) {
41        return x*other.y - y*other.x;
42    }
43    ll crossSign(Point other) {
44        ll res = this->cross(other);
45        if(res > 0) return 1;
46        else if(res < 0) return -1;
47        return 0;
48    }
49    ll dist(Point other) {
50        return pow(x-other.x,2) + pow(y-other.y,2);
51    }
52    Point operator-(Point other) const {
53        return Point(x-other.x, y-other.y);
54    }
55    bool operator<(Point other) const {
56        if(x == other.x) return y < other.y;
57        return x < other.x;
58    }
59    void print() {
60        cout << x << ' ' << y << ' ';
61    }
62};
63
64bool isIntersect(Point p1, Point p2, Point p3, Point p4) {
65    ll p1p2 = (p2-p1).crossSign(p3-p2) * (p2-p1).crossSign(p4-p2); // 선분 p1p2 기준
66    ll p3p4 = (p4-p3).crossSign(p1-p4) * (p4-p3).crossSign(p2-p4); // 선분 p3p4 기준
67
68    // 두 직선이 일직선 상에 존재
69    if(p1p2 == 0 && p3p4 == 0) {
70        if(p2 < p1) swap(p1,p2);
71        if(p4 < p3) swap(p3,p4);
72        return p3 < p2 && p1 < p4;
73    }
74    return p1p2 <= 0 && p3p4 <= 0;
75}
76
77struct Cut {
78    ll sx, sy, ex, ey, w;
79};
80
81int N;
82ll ans = 0;
83
84void solve() {
85    cin >> N;
86    ve<Cut> v(N);
87    for(int i=0; i<N; i++) {
88        cin >> v[i].sx >> v[i].sy >> v[i].ex >> v[i].ey >> v[i].w;
89        ans += v[i].w;
90    }
91
92    for(int i=0; i<N; i++) {
93        for(int j=i+1; j<N; j++) {
94            if(!isIntersect({v[i].sx,v[i].sy}, {v[i].ex,v[i].ey}, {v[j].sx,v[j].sy}, {v[j].ex,v[j].ey})) continue;
95            ans += min(v[i].w, v[j].w);
96        }
97    }
98
99    cout << ans << endl;
100}
101
102int main(void) {
103    ios_base::sync_with_stdio(false);
104    cin.tie(nullptr);
105    cout.tie(nullptr);
106
107    int TC=1;
108//    cin >> TC;
109    FOR(tc, 1, TC) {
110//        cout << "Case #" << tc << ": ";
111        solve();
112    }
113
114
115    return 0;
116}