boj, 백준) 12781. PIZZA ALVOLOC ( C / C++)

1. 문제 링크

www.acmicpc.net/problem/12781

12781번: PIZZA ALVOLOC

2. 문제 개요

볼록 다각형 모양인 피자에서 정점 네 개를 선택하여, 2개의 선분을 만든다. 이 선분이 서로 교차하여 피자가 4조각으로 잘리게 되면 1, 그렇지 않으면 0을 출력하는 프로그램을 작성하자

3. 문제 힌트

선분 교차 알고리즘이다. CCW(외적)을 이용해서 문제를 해결한다.

 

더 복잡한 2차원 평면에서의 선분교차가 아니고, 볼록 다각형 모서리에서의 정점을 선택하기 때문에 많은 제약이 삭제된다.

 

종이 위에 여러 선분을 그려보면서 어떻게 CCW를 활용해서 선분이 교차한다는 것을 알 수 있을까 생각해보자.

 

4. 문제 풀이

출처 : boj

볼록 다각형에서의 선분은 위와 같이 두 가지로 나타낼 수 있겠다. 그림 1 같은 경우는 두 선분이 교차하여,

선분 1->2, 그리고 가상의 선분 1->3 이 두 개의 선분(벡터)를 CCW한 것과,

선분 1->2, 가상의 선분 1->4 이 두개의 선분(벡터)를 CCW한 것의 부호가 반대이다. 

왜냐하면 선분 1->2에 대해서, 1->3은 시계방향(음의 값), 1->4는 반시계 방향(양의 값)을 반환하기 때문.

 

그렇다면, 부호가 반대이기 때문에 두 CCW한 값을 곱하게 되면 음수가 되고 교차하는 것을 알 수 있다.

 

그림 2를 보자.

그림 2는 선분 1->2에 대해서 1->3, 1->4가 모두 반시계의 방향에 있다.

그래서 CCW를 곱하면 양수가 되고, 교차하지 않는다는 것을 알 수 있다.

 

위의 방법은 볼록 다각형에서 두 선분을 연결하기 때문에 이렇게 간단한 케이스만 살펴보고 바로 문제를 풀 수 있다.

 

 

하지만 2차원 평면에서 서로 선분이 겹치는 경우나, 조금 복잡한 경우가 있는데, 다른 훌륭하신 분들이 블로그에 잘 정리해 놓은 것이 많기 때문에.. 구글에 검색하는 것을 추천합니다.

 

5. 코드

#include <cstdio>
using namespace std;

struct POINT {
	int x, y;
};

int ccw(POINT a, POINT b, POINT c) {
	int ret = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);

	if (ret > 0)
		return 1;
	else if (ret < 0)
		return -1;
	else
		return 0;
}

int main()
{
	POINT pt[4];
	
	for (int i = 0; i < 4; ++i)
		scanf("%d %d", &pt[i].x, &pt[i].y);

	if (ccw(pt[0], pt[1], pt[2])*ccw(pt[0], pt[1], pt[3]) < 0)
		printf("1");
	else
		printf("0");

	return 0;
}

6. 결과