[BOJ / 그리디 선분교차] 25315 N수매화검법

https://www.acmicpc.net/problem/25315

25315번: N수매화검법

 

25315 N수매화검법

알고리즘 : 그리디 / CCW(선분교차판정)

문제 티어 : 골드 II

2022 UCPC 예선에서 총 세 문제 풀이를 시도하였는데 솔브된 문제 중 유일하게 혼자 푼 문제이다. 여러번의 베기를 통해 이후 행할 겹치는 베기의 수만큼 추가 내공이 필요로 하기 때문에 그리디하게 작은 내공을 가진 베기부터 수행한다. (어차피 순서에 상관없이 겹치기 때문에) 선분 교차 판정은 CCW를 이용해서 각 점을 통해 자르게 되는데, 대회 중 온라인 서치가 가능해서 다른 사람의 소스를 이용하여 구현하였다. 각 가중치가 10^9까지기 때문에 long long int를 이용해서 처리한다.

이 문제는 어떤 세 점도 같은 직선 위에 있지 않다고 명시해주었는데, 같은 직선에 존재할 수 있을 경우 다르게 처리해주어야한다.

선분교차판정때문에 티어가 높게 산정된 듯한데 그리디 문제 자체는 실버1~골드5 사이정도의 난이도가 아닐까 싶다.

 

< CODE >

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
typedef long long int ll;

struct knife {
    ll sx;
    ll sy;
    ll ex;
    ll ey;

    knife() {

    }

    knife(int sx, int sy,int ex,int ey) {
        this->sx = sx;
        this->sy = sy;
        this->ex = ex;
        this->ey = ey;
    }
};

struct point {
    ll x;
    ll y;
};

pair<ll, knife> p[2505];

bool operator<(const knife& a, const knife& b) {
    return false;
}

int ccw(point a, point b, point c) {
    ll temp = a.x * b.y + b.x * c.y + c.x * a.y;
    temp -= a.x * c.y + b.x * a.y + c.x * b.y;

    if (temp > 0)
        return 1;
    else if (!temp)
        return 0;
    else
        return -1;
}

bool isOverlapped(knife a, knife b) {
    int ans1 = ccw({ a.sx, a.sy }, { a.ex,a.ey }, { b.sx,b.sy }) * ccw({ a.sx, a.sy }, { a.ex,a.ey }, { b.ex,b.ey });;
    int ans2 = ccw({ b.sx, b.sy }, { b.ex,b.ey }, { a.sx,a.sy }) * ccw({ b.sx, b.sy }, { b.ex,b.ey }, { a.ex,a.ey });

    return (ans1 < 0) && (ans2 < 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    
    cin >> n;

    for (int i = 0; i < n; i++) {
        int sx, sy, ex, ey, w;

        cin >> sx >> sy >> ex >> ey >> w;
        p[i] = make_pair(w, knife(sx,sy,ex,ey));
    }

    sort(p, p + n);

    ll result = 0;

    for (int i = 0; i < n; i++) {
        result += p[i].first;
        ll cnt = 0;
        for (int j = i + 1; j < n; j++) {
            if (isOverlapped(p[i].second, p[j].second)) {
                cnt++;
            }
        }
        result += cnt * p[i].first;
    }

    cout << result << '\n';
    return 0;
}

시간 : 56ms

 

태그 : #UCPC 25315 #BOJ 25315 #백준 25315 #2022 UCPC B