[C++]지민이의 테러 - 백준1688

문제

• 지민이의 테러(백준1688)

풀이

문제 해석을 하자면,

• 다각형 포함 계산 문제이다.
  • 다각형 내부에 점 포함 관련 응용 문제

풀이

• 교차점 개수가 홀수이면 내부 점이라고 판단.
• 교차점 구할때 처리할 부분?
  1. 에지(다각형 표면선)에 점이 존재하나 판단(맞다면 내부 점 아니라고 결정)
  2. 범위 비교로 다각형 내부에 점 존재하나 판단 (컴퓨터그래픽스 알고리즘 개념 정리 게시글 참고)
• (수정) 1번 풀이 경우 내부 점 맞다고 결정해야한다. 문제에서 보니까 조건이 있었는데 이를 한참뒤에 봤네ㅠㅠ
  • 조건 : “다각형 경계위에 있는 경우에는 보호되는 것이다.”

코드

#include<iostream>
using namespace std;

struct point {
	long long x; long long y;
};
typedef point Point;


long long ccw2(Point p, Point q) {
	return p.x * q.y - p.y * q.x;
}

long long ccw(Point r, Point p, Point q) {
	// r만큼 빼서 원점으로 이동 (ccw2 계산 위해)
	p.x -= r.x;
	p.y -= r.y;
	q.x -= r.x;
	q.y -= r.y;
	return ccw2(p, q);
}


// 점 c가 a,b직선 상에 존재하는지 판별함수
bool between(Point a, Point b, Point c) {
	// 1. 일직선 상에 존재하나 확인
	if (ccw(a, b, c) != 0) return false;
	else {
		// 2. 수직 여부 확인 후 범위제한
		if (a.x == b.x) {
			if ((c.y >= a.y && c.y <= b.y) || (c.y >= b.y && c.y <= a.y)) return true;
		}
		else {
			if ((c.x >= a.x && c.x <= b.x) || (c.x >= b.x && c.x <= a.x)) return true;
		}
		return false;
	}
}

bool leftTurn(Point a, Point b, Point c) {
	return ccw(a, b, c) > 0;
}

bool insidePolygon(Point q, Point P[], int N) {
	int crossing = 0;
	for (int i = 0; i < N; i++) {
		int ret = (i + 1) % N; // index N때 0으로 반환
		// 1. 에지(다각형 표면선)에 점이 존재하나 판단
		if (between(P[i], P[ret], q)) return true; // (수정) 문제에서 경계면도 포함하라 했음
		// 2. 범위 비교로 다각형 내부에 점 존재하나 판단
		if ((P[i].y < q.y && P[ret].y >= q.y && leftTurn(P[i], P[ret], q)) ||
			(P[ret].y < q.y && P[i].y >= q.y && leftTurn(P[ret], P[i], q)))
			crossing++;
	}
	if (crossing % 2 != 0) return true; // 교차점 개수가 홀수는 true
	return false;
}


Point barier[10005];
Point friends[3];

int main() {
	// input
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> barier[i].x >> barier[i].y;
	for (int i = 0; i < 3; i++) cin >> friends[i].x >> friends[i].y;

	// run & output
	for (int i = 0; i < 3; i++) {
		if (insidePolygon(friends[i], barier, N)) cout << 1 << '\n';
		else cout << 0 << '\n';
	}

	return 0;
}

느낀점

생략