[백준 16491] 대피소 찾기

문제 링크 => 16491번: 대피소 찾기 (acmicpc.net)

16491번: 대피소 찾기

---

CCW 를 이용하는 문제이다.

 

대피소를 연결할 수 있는 모든 경우의 수 N! 를 permutation 을 통해서 구할 수 있고, 로봇과 대피소를 연결한 벡터 N개에 대하여 ((N-1)N / 2) 개 일때 모두 선분 교차가 일어나지 않는 경우 해당 대피소의 번호를 출력하면 된다.

 

일직선 위에 점이 존재하지 않는다는 조건이 없으므로 [백준 17386] 선분 교차 1 :: M - J - C (tistory.com) 이 문제에서 추가로 살펴봐야 하는 점이 있다.

 

점 A를 임의의 로봇1 의 좌표, 점 B를 임의의 대피소1 의 좌표, 점 C를 임의의 로봇2 의 좌표, 점 D를 임의의 대피소2 의 좌표라고 가정한다.

 

그렇다면 CCW1 = CCW(A, B, C) * CCW(A, B, D), CCW2 = CCW(C, D, A) * CCW(C, D, B) 라고 할 때,  CCW1 값과 CCW2 값이 동시에 음수인 경우는 선분 교차임이 확실하다.

 

그렇다면 일직선 위에 점이 존재하지 않는다는 조건 없기 때문에 CCW1, CCW2 값이 동시에 0 인 경우를 살펴봐야 한다. (일직선인 경우)

 

즉, AB 의 x좌표와 CD 의 x 좌표가 겹치는지, 그리고 AB 의 y 좌표와 CD 의 y 좌표가 겹치는지를 확인해야 한다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

class Mars {
public:
	int rX, rY, sX, sY, idx;
	Mars(int rX, int rY, int sX, int sY, int idx) {
		this->rX = rX, this->rY = rY;
		this->sX = sX, this->sY = sY;
		this->idx = idx;
	}
};

class Shelter {
public:
	int sX, sY, idx;
	Shelter(int sX, int sY, int idx) {
		this->sX = sX, this->sY = sY;
		this->idx = idx;
	}
};

int N;
vector<pair<int, int>> robot;
vector<Shelter> shelter;

void input() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		robot.push_back({ x,y });
	}

	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		shelter.push_back({ x,y,i + 1 });
	}

}

int getCross(pair<int, int> x, pair<int, int> y) {
	int ret = x.first * y.second - x.second * y.first;
	if (ret > 0) return 1;
	else if (ret == 0) return 0;
	else return -1;
}

int disjoint(int s, int e, int l, int r) {
	if (s > e) swap(s, e);
	if (l > r) swap(l, r);
	return e<l || s>r;
}

int isSafe(Mars m1, Mars m2) {

	pair<int, int> v1, v2, v3;
	int x_1, x_2, x_3, x_4;
	int y_1, y_2, y_3, y_4;
	int CCW1, CCW2;

	x_1 = m1.rX, x_2 = m1.sX, x_3 = m2.rX, x_4 = m2.sX;
	y_1 = m1.rY, y_2 = m1.sY, y_3 = m2.rY, y_4 = m2.sY;

	v1.first = x_2 - x_1, v1.second = y_2 - y_1;
	v2.first = x_3 - x_1, v2.second = y_3 - y_1;
	v3.first = x_4 - x_1, v3.second = y_4 - y_1;

	CCW1 = getCross(v1, v2) * getCross(v1, v3);

	v1.first = x_4 - x_3, v1.second = y_4 - y_3;
	v2.first = x_1 - x_3, v2.second = y_1 - y_3;
	v3.first = x_2 - x_3, v3.second = y_2 - y_3;

	CCW2 = getCross(v1, v2) * getCross(v1, v3);

	if (CCW1 == 0 && CCW2 == 0) {
		return !(!disjoint(x_1, x_2, x_3, x_4) && !disjoint(y_1, y_2, y_3, y_4));
	}
	return !(CCW1 < 0 && CCW2 < 0);
}

void solve() {
	
	vector<int> tmp;
	for (int i = 0; i < N; i++) tmp.push_back(i);

	do {
		vector<Mars> v;
		int total = 0;

		for (int i = 0; i < N; i++) {
			int x_1 = robot[i].first, y_1 = robot[i].second;
			int x_2 = shelter[tmp[i]].sX, y_2 = shelter[tmp[i]].sY;
			int idx = shelter[tmp[i]].idx;
			v.push_back({ x_1,y_1,x_2,y_2,idx });
		}

		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N; j++) {
				if (isSafe(v[i], v[j])) total++;
			}
		}

		if (total == (N * (N - 1)) / 2) {
			for (int i = 0; i < N; i++) {
				cout << v[i].idx << endl;
			}
			return;
		}

	} while (next_permutation(tmp.begin(), tmp.end()));

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}