글 읽기 - 반례가 생각나지 않아 질문합니다.

donggunseo 4년 전 0

intersect 여부를 파악하는 것까지는 잘 했다고 생각하는데 WA가 뜨는 거 보면 백트래킹부분에서 문제가 있지 않을까 싶네요. 네트워크 유량 알고리즘으로 대부분 많이 푸시던데 백트래킹으로도 가능하다고 생각하여 이렇게 짜봤는데 혹시 반례가있다면 알려주실수 있을까요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;



vector<pair<int, int>> corner, hole, mouse;
int n, k, h, m;
int visited[50];
vector<int> available_hole[250];

int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
	int op = a.first * b.second + b.first * c.second + c.first * a.second;
	op -= (a.second * b.first + b.second * c.first + c.second * a.first);
	if (op > 0) return 1;
	else if (op == 0) return 0;
	else return -1;
}

bool intersect(pair<int, int> H, pair<int, int> M)
{
	for (int i = 0; i < n; ++i)
	{
		int j;
		if (i == n - 1) j = 0;
		else j = i + 1;

		if (i % 2 == 0)
		{
			if (H.second == corner[i].second && min(corner[i].first, corner[j].first) <= H.first && H.first <= max(corner[i].first, corner[j].first))
				continue;
		}
		else
		{
			if (H.first == corner[i].first && min(corner[i].second, corner[j].second) <= H.second && H.second <= max(corner[i].second, corner[j].second))
				continue;
		}
		pair<int, int> temp1 = corner[i];
		pair<int, int> temp2 = corner[j];
		pair<int, int> temp3 = H;
		pair<int, int> temp4 = M;
		int ab = ccw(H, M, corner[i]) * ccw(H, M, corner[j]);
		int cd = ccw(corner[i], corner[j], H) * ccw(corner[i], corner[j], M);
		if (ab == 0 && cd == 0)
		{
			if (temp3 > temp4) swap(temp3, temp4);
			if (temp1 > temp2) swap(temp1, temp2);
			if (temp1 <= temp4 && temp3 <= temp2)
			{
				return true;
			}
		}
		if (ab <= 0 && cd <= 0)
		{
			return true;
		}
	}
	return false;
}

void backtracking(int mouse_n)
{
	if (mouse_n == m)
	{
		cout << "Possible" << endl;
		exit(0);
	}
	int size = available_hole[mouse_n].size();
	for (int j = 0; j < size; ++j)
	{
		if (visited[available_hole[mouse_n][j]] == 0)
		{
			continue;
		}
		visited[available_hole[mouse_n][j]] -= 1;
		backtracking(mouse_n + 1);
		visited[available_hole[mouse_n][j]] += 1;
	}
}


bool solution()
{
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < h; ++j)
		{
			if (!intersect(hole[j], mouse[i]))
			{
				available_hole[i].push_back(j);
			}
		}

		if (available_hole[i].size() == 0)
		{
			return false;
		}
	}
	backtracking(0);
	return false;
}

int main()
{
	cin >> n >> k >> h >> m;
	for (int i = 0; i < n; ++i)
	{
		int p1, p2;
		cin >> p1 >> p2;
		corner.push_back(pair<int, int>(p1, p2));
	}
	for (int i = 0; i < h; ++i)
	{
		int p1, p2;
		cin >> p1 >> p2;
		hole.push_back(pair<int, int>(p1, p2));
	}
	for (int i = 0; i < m; ++i)
	{
		int p1, p2;
		cin >> p1 >> p2;
		mouse.push_back(pair<int, int>(p1, p2));
	}
	for (int i = 0; i < h; ++i)
	{
		visited[i] = k;
	}
	if (!solution())
	{
		cout << "Impossible" << endl;
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례가 생각나지 않아 질문합니다.

donggunseo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말