[PS] N수매화검법 / C++ (백준 25315번)

 

2022 UCPC 예선 B번, 그리디로 풀 수 있는 선분 교차 판정 문제로, N <= 2500 이므로 O($n^{2}$)도 가능하다.

 

해결 방법

 가중치를 기준으로 정렬한 뒤 가중치가 낮은 베기부터 ccw 알고리즘으로 교차되는 선분의 개수를 구하여 가중치에 곱한 값을 모두 더하여 답을 도출했다.

[알고리즘] CCW(Counter Clockwise) 알고리즘

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
struct Point {
    ll x1, y1, x2, y2, w, m;
};

bool cmp(struct Point a, struct Point b) {
    return a.w < b.w;
}

Point d[2501];

int ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
    ll temp = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    if (temp < 0)return -1;
    if (temp > 0)return 1;
    return 0;
}

bool isIntersect(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4) {
    int ccw1 = ccw(x1, y1, x2, y2, x3, y3);
    int ccw2 = ccw(x1, y1, x2, y2, x4, y4);
    int ccw3 = ccw(x3, y3, x4, y4, x1, y1);
    int ccw4 = ccw(x3, y3, x4, y4, x2, y2);

    return (ccw1 * ccw2 < 0) && (ccw3 * ccw4 < 0);
}

int main() {
    ll n, dap = 0;
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld %lld %lld %lld", &d[i].x1, &d[i].y1, &d[i].x2, &d[i].y2, &d[i].w);
    }
    sort(d, d + n, cmp);
    for (int i = 0; i < n; i++) {
        d[i].m = 0;
        for (int j = i + 1; j < n; j++) {
            if (isIntersect(d[j].x1, d[j].y1, d[j].x2, d[j].y2, d[i].x1, d[i].y1, d[i].x2, d[i].y2)) {
                d[i].m++;
            }
        }
        dap += d[i].w * (d[i].m + 1);
    }
    printf("%lld\n", dap);
    return 0;
}