취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21430번 문제인 Свечки이다.
문제는 아래 링크를 확인하자.

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

어떤 직선과 그 직선 위에 놓여있지 않은 점에 대하여, 점이 직선의 어느 쪽에 있느냐에 따라 $ax+by+c$의 부호가 변한다는 점을 관찰하자. 또한 직선으로 나뉘어진 각 영역은 각 직선에 대하여 어느 쪽에 있는지를 모두 기록한 것으로 구분된다는 점을 관찰하자.

이를 이용하면, $m$개의 비트를 이용하여 각 직선마다 어느 쪽에 점이 있는지를 기록할 수 있게 된다. 이 중 중복되는 값이 있는지를 살펴 문제를 해결하자.

각 직선을 비트로 저장하는 대신 trie 자료구조를 활용해도 좋다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;

int N, M, R;
int P[10000][2];
vector<bool> st[10000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> R;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) st[i].resize(M);
    for (int j = 0; j < M; j++) {
        int A, B, C; cin >> A >> B >> C;
        for (int i = 0; i < N; i++) {
            if (A * P[i][0] + B * P[i][1] + C > 0) st[i][j] = 1;
        }
    }
    sort(st, st + N);
    for (int i = 0; i + 1 < N; i++) {
        if (st[i] == st[i + 1]) {
            cout << "YES";
            return 0;
        }
    }
    
    cout << "NO";
}