[BOJ] 백준 2650 교차점개수 (KOI 1998 초등부)

문제 링크

www.acmicpc.net/problem/2650

2650번: 교차점개수

 

풀이

세 직선이 한 점에서 교차하면 안되고, 원하는대로 곡선을 그릴 수 있습니다. 

항상 하나의 교차점에서 두 선만 교차하므로 모든 선에 대해 $O(N^2)$으로 교차 여부를 판별하면 됩니다.

 

문제에서는 직사각형을 줬는데, 이를 원으로 생각하면 쉽게 풀 수 있습니다.

모든 점을 적당한 연산을 통해 원 위의 한 점으로 바꿔주고, 선을 이루는 두 점을 페어로 저장합니다. 이때 항상 좌표가 작은 점이 앞에 오도록 저장합니다. (line 21 ~ 25)

 

 

 

 

 

그림을 보고 교차 조건을 유추할 수 있습니다.

$\overline{ab}$ 입장에서 $a < c\ and\ c < b\ and\ b < d$ 이면 항상 두 선이 교차합니다.

이를 이용해 정답을 구해주면 됩니다.

 

정답 코드

#include <bits/stdc++.h>

#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using pii = pair<int, int>;

vector<pii> p;
int n;
int to[5] = {0, 0, 2, 3, 1};

int main() {
    cin >> n;
    n /= 2;
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a = to[a];
        c = to[c];
        int x = a * 51 + b, y = c * 51 + d;
        if (a > 1) x += 51 - 2 * b;
        if (c > 1) y += 51 - 2 * d;

        p.emplace_back(min(x, y), max(x, y));
    }
    int ans = 0;
    int cross[55] = {0,};
    for (int i = 0; i < n; i++) {
        auto[a, b] = p[i];
        for (int j = 0; j < n; j++) {
            auto[c, d] = p[j];
            if (a < c && c < b && b < d) {
                ans++;
                cross[i]++;
                cross[j]++;
            }
        }
    }
    cout << ans << endl;
    cout << *max_element(cross, cross + n);
}