[1688] 지민이의 테러

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

1688번: 지민이의 테러

다각형 밖의 임의의 점 하나를 잡고, 다각형 내에 존재하는지 판단 대상이 되는 점과의 선분을 만든다.

다각형을 구성하는 n개의 선분과 교차하는 횟수가 홀수번이라면 다각형 내의 점이 된다.

 

다각형의 경계 위에 있는 경우를 위 방식으로 잡아내지 못하므로 별도로 체크하고,

다각형 밖의 임의의 점과 그은 선분이 기존 다각형을 구성하던 선분과 평행하지 않도록 잡았다.

---

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using pi = pair<ll, ll>;

using pii = pair<pi, pi>;

#define x first

#define y second

ll ccw(const pi& a, const pi& b, const pi& c) {

    ll ret = 0;

    ret += (a.x * b.y + b.x * c.y + c.x * a.y);

    ret -= (b.x * a.y + c.x * b.y + a.x * c.y);

    return ((ret > 0) ? 1 : (ret == 0) ? 0 : -1);

}

bool f(pi A, pi B, pi C, pi D) {

    ll p = ccw(A, B, C) * ccw(A, B, D);

    ll q = ccw(C, D, A) * ccw(C, D, B);

    if (p == 0 and q == 0) {

        if (A > B) swap(A, B);

        if (C > D) swap(C, D);

        return (A <= D and C <= B);  // A-C-B-D

    }

    return (p <= 0 and q <= 0);

}

ll n;

vector<pi> v;

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

    v.resize(n + 1);

    ll i, j;

    for (i = 0; i < n; i++) cin >> v[i].x >> v[i].y;

    v[n] = v[0];

    pi base = {1, 1'000'000'001};

    for (i = 0; i < 3; i++) {

        ll cnt = 0;

        pi cur;

        cin >> cur.x >> cur.y;

        for (j = 0; j < n; j++) {

            if (ccw(cur, v[j], v[j + 1]) == 0 and min(v[j], v[j + 1]) <= cur and

                cur <= max(v[j], v[j + 1])) {

                cnt = 1;

                goto skip;

            }

        }

        for (j = 0; j < n; j++) cnt += f(v[j], v[j + 1], base, cur);

    skip:

        cout << (cnt & 1LL) << '\n';

    }

    return 0;

}

---