-
[1688] 지민이의 테러BOJ 2022. 7. 16. 16:42
https://www.acmicpc.net/problem/1688
1688번: 지민이의 테러
첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있
www.acmicpc.net
다각형 밖의 임의의 점 하나를 잡고, 다각형 내에 존재하는지 판단 대상이 되는 점과의 선분을 만든다.
다각형을 구성하는 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 secondll 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 andcur <= 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;}
'BOJ' 카테고리의 다른 글
[10999] 구간 합 구하기 2 (0) 2022.07.26 [13306] 트리 (0) 2022.07.20 [14907] 프로젝트 스케줄링 (0) 2022.07.04 [2585] 경비행기 (0) 2022.06.23 [1504] 특정한 최단 경로 (0) 2022.06.21