문해기 2번 과제

과제 2: 파란 점 하얀 점

2차원 좌표평면 (0, 0) 부터 (N, N) 안에 M개의 하얀 점이 있다. 점의 X, Y 좌표는 0 이상 N 이하인 정수임에 유의하라. 이 점 중 일부의 점을 파란 색으로 바꾸어 칠하려고 한다. 파란 점들을 이은 다각형을 만들었을 때, 이 다각형의 바깥에 하얀 점이 없게 하려고 하고, 또한 가장 적은 개수의 하얀 점을 파란 색으로 바꾸어 칠하려고 한다. 또한, 셋 이상의 점이 한 직선 위에 있는 경우는 없다. 

 

좌표 평면의 크기 N, 하얀 점의 수 M이 주어졌을 때, 위 조건을 만족하는 파란 점의 개수를 출력하는 프로그램을 작성하시오. 

 

입력 

표준 입력으로 입력을 받는다. 첫 줄에는 좌표 평면의 크기 N, 하얀 점의 수 M이 주어진다. N은 unsigned int로 표현 가능한 범위 이내인 정수이며, M은 10만 이하이다. 다음 N 줄에는 차례대로 하얀 점의 좌표를 나타내는 두 정수  X Y가 주어지는데, X, Y는 0 이상 N 이하인 정수이다. 단, 프로그램 구현 과정에서 unsigned int로 표현 가능하지 않은 값이 나올 수 있지만, long long이나 int64 등 64비트 정수 이내에서 처리할 수 있다는데 유의하시오.  

 

출력 

표준 출력으로 출력한다. 한 줄에 하나의 정수를 출력하는데, 파란 점의 개수를 나타낸다.  

 

예제 입력 1

100 6

1 1 

2 3 

1 5

5 5

4 3

5 1

예제 출력 1

4 

예제 입력 2

100 4

3 3 

6 3

1 1 

4 1

예제 출력 2

4

 

컨벅스 헐 문제이다. 이 문제랑 똑같은 문제가 백준에 있으니 참고 바란다.

#include <iostream>
#include <vector>
#include <wingdi.h>

using namespace std;


typedef unsigned long long ull;

struct vector2 {
	ull x, y;
};

typedef vector<vector2> polygon;

bool isInside(vector2 B, const polygon& p) {
	ull crosses = 0;
	for (ull i = 0; i < p.size(); i++) {
		ull j = (i + 1) % p.size();
		if ((p[i].y > B.y) != (p[j].y > B.y)) {
			long double atX = long double(p[j].x - p[i].x) * long double(B.y - p[i].y) / long double(p[j].y - p[i].y) + long double(p[i].x);
			
			if (B.x < atX) {
				crosses++;
			}
		}
	}
	return crosses % 2 > 0;
}

void pick(ull n, vector<ull>& picked, ull toPick, vector<polygon>& toSearch, polygon input) {
	if (toPick == 0) {	
		polygon tmp;
		for (auto& v : picked) {
			vector2 tmp_v;
			tmp_v.x = input[v].x;
			tmp_v.y = input[v].y;
			tmp.push_back(tmp_v);
		}
		toSearch.push_back(tmp);
	}

	ull smallest = picked.empty() ? 0 : picked.back() + 1;
	
	for (ull next = smallest; next < n; ++next) {
		picked.push_back(next);
		pick(n, picked, toPick - 1, toSearch, input);
		picked.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	ull N, M;
	cin >> N >> M;
	polygon arr;
	for (ull i = 0; i < M; i++) {
		ull x, y;
		cin >> x >> y;
		vector2 tmp{ x,y };
		//cout << tmp.x << " " << tmp.y << endl;
		arr.push_back(tmp);
	}
	for (ull i = 3; i < M; i++) {
		vector<ull> picked;
		vector<polygon> toSearch;
		pick(M, picked, i, toSearch, arr);
		//testcode

		

		for (ull j = 0; j < toSearch.size(); j++) {
			for (ull k = 0; k < i; k++) {
				ull cnt = 0;
				polygon test;
				for (ull z = 0; z < arr.size(); z++) {
					if (isInside(arr[z], toSearch[k])) {
						test.push_back(arr[z]);
						cnt++;
					}
						
				}
				if (cnt == M-i) {
					cout << i << endl;
					for (ull x = 0; x < toSearch[j].size(); x++) {
						cout << "x : " << toSearch[j][x].x << " y : " << toSearch[j][x].y << endl;

					}
					cout << "\n------------------------------\n";
					for (ull x = 0; x < test.size(); x++) {
						cout << test[x].x << " " << test[x].y << "\n";
					}
					cout << "\n--------------\n";
					return 0;
				}
			}
		}
	}
	cout << M << endl;
	return 0;
}