Boj 24895) 다트

문제

백준 24895

설명

볼록껍질의 성질을 적극적으로 활용해야하는 문제이다.

아래에선 두 단계를 거쳐서 문제를 푼다.

1. 두 접점을 구한다.
2. 점수를 구한다.

접점 구하기

임의의 점 \(Q\) 가 주어진 다각형 안에 있는지 판단하는 방법은 모든 선분에 대해서 선분과 점 \(Q\) 가 이루는 삼각형이 시계반대방향인지 체크하는 것이다. 만약 밖에 있다면 어떤 선분은 시계방향으로 삼각형을 이룰 것이다. 또한 볼록껍질의 특성 상 이러한 특징을 갖는 선분은 서로 인접한다. 다시말해 다각형은 삼각형을 시계방향으로/반대방향으로 이루는 두 부분으로 나뉘어 질 것이다.

우리는 \(Q\) 와 시계방향으로 삼각형을 이루는 어떤 선분이 존재하는지, 존재한다면 어떤 선분인지, 이분탐색으로 빠르게 구할 수 있다.

볼록껍질의 특성 때문에 주어진 다각형의 임의의 점 \(P_O\) 에 대해서 다른 정점들은 반드시 시계반대방향 순서로 정렬되어 있다. 다른 정점들의 양 끝을 넘어서지 않는다면 \(Q\) 가 변 \(\overline{P_S P_E}\) 에 대해서 \(P_S \leq Q \leq P_E\) 가 시계반대방향 순서로 성립하는지는 이분탐색으로 빠르게 구할 수 있다.

만약 이 변에 대해서 외적이 양수라면 \(Q\) 는 다각형 안에 있게 된다. 그렇지 않다면 이 변의 양쪽으로 나아가다 보면 접점이 나올 것이다.

다른 정점들의 양 끝을 넘는 범위에 대해서는 적절한 예외처리를 통해 확인할 수 있다.

나머지는 코드의 주석을 참고하자.

점수 구하기

두 접점이 주어져 있다면 누적합을 통해 빠르게 넓이를 구할 수 있다.

임의의 두 꼭짓점 \(P_A, P_B\) 에 대해 다각형을 쪼개야한다고 하자. 우선 다각형을 그것을 이루는 꼭짓점 중 임의의 점 \(P_O\) 을 공통으로 지나는 삼각형으로 쪼갠다. 그러면 다각형은 삼각형 \(\{P_O, P_A, P_B\}\) 와 양쪽의 두 다각형 \(\{P_O, P_{O+1}, ..., P_{A-1}, P_A, P_O\}\), \(\{P_O, P_B, P_{B+1}, ..., P_{O-1}, P_O\}\), 으로 나눌 수 있다. 앞의 삼각형은 외적으로 뒤의 두 다각형은 누적합으로 구하면 상수시간에 점수를 구할 수 있다.

주의해야할 점은 나뉘는 두 영역 중 최솟값이라는 것이다.

시간 복잡도

= \(\mathsf{O}(\mathrm{M} \log{\mathrm{N}})\)

코드

using ll = long long;
const ll MOD = 1e9 + 7;
struct VEC
{
    ll x, y;
    bool operator==(const VEC& in) const { return x == in.x && y == in.y; }
    VEC operator-(const VEC& p) const { return { x - p.x, y - p.y }; }
    ll dot(const VEC& p) { return x * p.x + y * p.y; }
    friend ll CCW(const VEC& a, VEC b, VEC c)
    {
        b = b - a;
        c = c - a;
        return  b.x * c.y - b.y * c.x;
    }
};

VEC pos[50001];  // ccw 으로 점 주어짐
ll sums[50001];
int n, m;

ll GetScore(int a, int b)
{
    if (b < a) swap(a, b);

    ll p1 = sums[a] - sums[1], p2 = sums[n - 1] - sums[b];
    ll p3 = CCW(pos[0], pos[a], pos[b]);
    ll p = p1 + p2 + p3;

    return min(p, sums[n - 1] - p);
}

int GetLeft(const VEC& cur, int s, int e)
{
    int r = e + 1;
    int os = s, oe = e;
    while (s <= e)
    {
        int m = (s + e) >> 1;

        auto vp = (pos[oe % n] - pos[os % n]).dot(pos[m % n] - pos[os % n]);
        auto vm = CCW(pos[m % n], pos[(m - 1 + n) % n], cur);

		// 원래는 바깥부분->안부분->바깥부분으로 되어있어 이분탐색이 되지 않는다.
		// 만약 vp <= 0 을 거르면 남은 부분은 바깥부분->안부분 으로만 나뉘어서 이분탐색이 가능하다.
        if (vm > 0 && vp > 0)
        {
            r = min(r, m);
            e = m - 1;
        }
        else s = m + 1;
    }
    return (r - 1) % n;
}

int GetRight(const VEC& cur, int s, int e)
{
    int r = s - 1;
    int os = s, oe = e;
    while (s <= e)
    {
        int m = (s + e) >> 1;

        auto vp = (pos[os % n] - pos[oe % n]).dot(pos[m % n] - pos[oe % n]);
        auto vm = CCW(pos[m % n], pos[(m + 1) % n], cur);

        if (vm < 0 && vp > 0)
        {
            r = max(r, m);
            s = m + 1;
        }
        else e = m - 1;
    }
    return (r + 1) % n;
}

void Do(const VEC& cur, int& l, int& r)
{
    int idx = lower_bound(pos + 1, pos + n, cur, [](auto& a, auto& b) { return CCW(pos[0], a, b) > 0; }) - pos;

	// 정점과 일치
    if (pos[idx % n] == cur || pos[0] == cur)
    {
        l = r = 0;
        return;
    }
	// 원점->시작점 혹은 원점->끝점 을 잇는 선 위에 cur 이 있는 경우
    else if (idx < n && CCW(pos[0], pos[idx % n], cur) == 0)
    {
        auto d = (pos[idx % n] - pos[0]).dot(cur - pos[idx % n]);
        if (idx == 1 && d < 0) idx--;        
        else if (idx == n - 1 && d > 0) idx--;
    }
    else idx--;

    int s = (idx + 1) % n, e = idx;
    if (e < s) e += n;

    l = GetLeft(cur, s, e);
    r = GetRight(cur, s, e);
}

ll Play()
{
    ll score = 0;

    for (int i = 0; i < m; i++)
    {
        VEC cur;
        cin >> cur.x >> cur.y;

        int l, r;
        Do(cur, l, r);

        ll test = CCW(pos[l], pos[r], cur);
        if (test > 0) score += sums[n - 1] % MOD;
        else if (test < 0) score += GetScore(l, r) % MOD;
        score %= MOD;
    }

    return score;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> pos[i].x >> pos[i].y;
    for (int i = 2; i < n; i++) sums[i] = sums[i - 1] + CCW(pos[0], pos[i - 1], pos[i]);

    ll a = Play(), b = Play();

    cout << (a == b ? "same" : a > b ? "ym" : "hb") << '\n';
    cout << a << ' ' << b;
}