[BOJ 12781] PIZZA ALVOLOC

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

12781번: PIZZA ALVOLOC

 

- 문제 요약

 

PIZZA

도윤이와 친구들은 볼록 다각형 모양의 피자를 아래와 같은 방법을 사용해서 4조각으로 나눠먹기로 했다.

1. 한 명씩 피자의 가장자리의 한 점을 선택한다. (같은 점을 선택하지 않는다.)
2. 선택한 순서대로 첫 번째 점과 두 번째 점을 이어 선분을 만들고 세 번째 점과 네 번째 점을 이은 선분을 만든다.
3. 만들어진 두 선분을 따라 피자를 자른다.

피자 조각의 크기는 똑같지 않아도 괜찮다. 4개의 점이 주어질 때 점을 이어서 피자를 4조각으로 만들 수 있는지 알아보는 프로그램을 만들어보자. 피자가 4조각으로 나눠지면 1, 아니면 0을 출력한다.

 

 

- 알고리즘 정리

 

2차원 평면에서의 CCW(선분 교차 판정)을 활용해서 문제를 해결하면 됩니다.

https://www.acmicpc.net/blog/view/27

점 3개의 방향성을 나타내는 CCW

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

pair<int,int>p[4];

int ccw(pair<int, int>p1, pair<int, int>p2, pair<int, int>p3) {
    int s = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
    s -= (p1.second * p2.first + p2.second * p3.first + p3.second * p1.first);

    if (s > 0) return 1;
    else if (s == 0) return 0;
    else return -1; 
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for(int i=0;i<4;i++){
		cin>>p[i].first>>p[i].second;
	}
	if(ccw(p[0],p[1],p[2])*ccw(p[0],p[1],p[3])<0){
		cout<<1;
	}
	else{
		cout<<0;
	}
}

코드 제출 결과