글 읽기 - [14750] Jerry and Tom 문의 드립니다.

anglermoon 4년 전 0

10255 교차점 문제를 먼저 풀고나서
아이디어를 얻고나서, 이분매칭 알고리즘을 응용하여 풀었으나
풀리지 않고 시간만 흘러 답답한 마음에 올려 봅니다.
고수님들의 의견 부탁드려요

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

int N, K, H, M; // k(1 ≤ k ≤ 5)

vector < pair <ll, ll> > NV; //  n(1 ≤ n ≤ 1,000) 
vector < pair <ll, ll> > HV; //  h(1 ≤ h ≤ 50)  
vector < pair <ll, ll> > MV; //  m(1 ≤ m ≤ k*h) 


vector < int > mouse[250 + 2];
vector < int > hole[50 + 2];

int visit[250 + 2];

int ccw(pair <ll, ll> A, pair <ll, ll> B, pair <ll, ll> C) {
	ll x1 = A.first;
	ll y1 = A.second;
	ll x2 = B.first;
	ll y2 = B.second;
	ll x3 = C.first;
	ll y3 = C.second;

	ll line1 = x1 * y2 + x2 * y3 + x3 * y1;
	ll line2 = y1 * x2 + y2 * x3 + y3 * x1;

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

int IsCross(pair <ll, ll> A, pair <ll, ll> B, pair <ll, ll> C, pair <ll, ll> D) {
	ll po1 = ccw(A, B, C); ll po2 = ccw(A, B, D);
	ll po3 = ccw(C, D, A); ll po4 = ccw(C, D, B);

	ll line1 = po1 * po2;
	ll line2 = po3 * po4;

	if (line1 == 0 && line2 == 0) {

		if (A > B) swap(A, B);
		if (C > D) swap(C, D);
		if (po1 == 0 && po2 == 0 && po3 == 0 && po4 == 0) {

			if (A < D && B > C) return -1;
			if (A == D || B == C) return 1;
			else return 0;
		}
		return 1;

	}

	return line1 <= 0 && line2 <= 0;
}



int dfs(int m) {
	if (visit[m] == 1) return 0; // 무한반복 제거
	visit[m] = 1;
	for (unsigned int i = 0; i < mouse[m].size(); i++) {
		int h_num = mouse[m][i];
		if (hole[h_num].size() < (unsigned int)K) {
			hole[h_num].push_back(m);
			return 1;
		}
		else{
			for (unsigned int j = 0; j < hole[h_num].size(); j++) {
				int mouse = hole[h_num][j];
				if (dfs(mouse)) {
					hole[h_num][j] = m;
					return 1;
				}
			}
		}
	}
	return 0;
}


int main() {
	cin.sync_with_stdio(false);
	cin >> N >> K >> H >> M;

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


	for (int i = 0; i < H; i++) { // HOLE
		ll x, y;
		cin >> x >> y;
		HV.push_back({ x,y });
	}

	for (int i = 0; i < M; i++) { // MOUSE
		ll x, y;
		cin >> x >> y;
		MV.push_back({ x,y });
	}

	for (int m = 0; m < M; m++) { // mouse
		for (int h = 0; h < H; h++) { // hole
			int cross = 0;
			for (int n = 0; n < N; n++) {
				int tmp = n != N - 1 ? IsCross(MV[m], HV[h], NV[n], NV[n + 1]) : IsCross(MV[m], HV[h], NV[n], NV[0]);

				if (tmp == -1) { cross = 0; break; }
				
				if (tmp) {
					cross++;
					if (IsCross(MV[m], HV[h], NV[n], NV[n])) { // hole 과 모서리가 같은지 본다.
						cross--;
					}					 
				}
			}
			if (cross == 1) {
				mouse[m].push_back(h);
			}
		}
	}


	int Ans = 0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j <= H; j++) visit[j] = 0;

		if (dfs(i)) Ans++;
	}

	if (Ans < M) cout << "Impossible" << endl;
	else cout << "Possible" << endl;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[14750] Jerry and Tom 문의 드립니다.

anglermoon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말