백준 14750 (C++) Jerry and Tom

최초 업로드: 2025-04-16 09:57:26

최근 수정 시간: 2025-07-25 09:49:25

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] Jerry and Tom

#### [문제 링크](https://www.acmicpc.net/problem/14750)

## 문제 설명

Naughty mouse Jerry and his friend mice sometimes visit a vacant house to play the famous children game ‘hide and seek’ and also to adjust the length of their teeth by gnawing furniture and chairs left there. If we look down the house from the sky the boundary of it composes an orthogonal polygon parallel to the xy-axes as shown in the figure below. In other words, every wall of the house is either horizontal or vertical.

Tom, a threatening cat to them, sometimes appears in the house while they are enjoying the game. In that case Jerry and his friends should hide into the rat’s holes at the bottom on the walls. There are two rules which must be held for them to hide into the holes:

<ol>
	<li>Each hole can afford at most k mice.</li>
	<li>Each mouse can enter the hole which can be seen by it. In other words, a mouse cannot enter the hole which is hidden by any wall. (That is, if the connecting line between a mouse and a hole intersects either any wall or any corner point of the house, the hole is considered hidden from the mouse.)</li>
</ol>

For example, consider a situation where three mice and three holes are in the house as shown in Figure E.1. Each circle on the boundary denotes a hole. Assuming that k = 1, i.e., only one mouse is allowed to hide into each hole, with the situation shown in the left figure, when Tom appears all the three mice can hide. But for the case shown in the right figure it is impossible for all the mice to hide.

Figure E.1: Illustration to show two situations: 1. All mice can hide (left) and 2. They cannot (right)

You can assume:

<ol>
	<li>Every mouse is strictly inside the house, which means that no mouse is on the wall</li>
	<li>Every hole is on the wall.</li>
	<li>No two holes locate at the same spot.</li>
	<li>No two mice locate at the same spot.</li>
</ol>

Given a situation explained above, you are to write a program which determines whether all the mice can hide or not.

## 입력

Your program is to read from standard input. The input starts with a line containing four integers, n, k, h, and m, where n(1 ≤ n ≤ 1,000) is the number of the corner points of a house, k(1 ≤ k ≤ 5) the maximum number of mice each hole can afford, h(1 ≤ h ≤ 50) the number of holes, m(1 ≤ m ≤ k ∙ h) the number of mice. In each of the following n lines, each coordinate of the corner points of the house is given in counter clockwise order. Each point is represented by two integers separated by a single space, which are the x- coordinate and the y-coordinate of the point, respectively. Each coordinate is given as an integer between -109 and 109, inclusively. In each of the following h lines, two integers x and y are given, which represent the coordinate (x, y) of each hole. In each of the following m lines, two integers x and y are given, which represent the coordinate (x, y) of each mouse.

## 출력

Your program is to write to standard output. Print exactly one line for the input. Print Possible if all the mice can hide into the rat’s holes holding the constraints explained above. Otherwise print Impossible.

## 풀이
#### 벽의 꼭짓점 위치를 받아서 모든 벽의 시작 좌표, 끝 좌표를 저장하고, 모든 쥐에 대해서 각각의 쥐가 갈 수 있는 구멍을 CCW로 확인하고, 에드몬드-카프 알고리즘으로 구해주었다. 특히 CCW 부분에서 반례 찾는 것이 어려웠다.

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

typedef long long ll; // 오버플로우 조심
const int INF = 0x3f3f3f3f;
const int MAX = 302;
const int S = MAX-2;
const int E = MAX-1;
int f[MAX][MAX], c[MAX][MAX];
int prv[MAX];

struct pos {
    ll x, y;
};

struct wall {
    ll x1, y1, x2, y2;
};

int n, k, h, m;
vector<wall> walls;
vector<vector<int>> conn(MAX);
vector<pos> hole(50), corner(1000), mouse(250);

bool oneLine(wall w1, wall w2) {
 return w1.x1!=w1.x2 && (max(w1.x1, w1.x2) < min(w2.x1, w2.x2) || max(w2.x1, w2.x2) < min(w1.x1, w1.x2))
 || w1.y1!=w1.y2 && (max(w1.y1, w1.y2) < min(w2.y1, w2.y2) || max(w2.y1, w2.y2) < min(w1.y1, w1.y2));
}

bool crossChk(wall w1, wall w2) { // 선분 교차 판정
    pos vec1 = {w1.x2-w1.x1, w1.y2-w1.y1};
    pos vec2 = {w2.x1-w1.x2, w2.y1-w1.y2};
    pos vec3 = {w2.x2-w1.x2, w2.y2-w1.y2};

ll a = vec1.x*vec2.y - vec2.x*vec1.y;
 ll b = vec1.x*vec3.y - vec3.x*vec1.y;
 return (a<0 && b<0 || a>0 && b>0 || a==0 && b==0 && oneLine(w1, w2)); // a=0, b=0인 경우는 두 선분이 일렬인 경우
}

bool isCorner(wall mouse, wall w) {
    return (mouse.x2==w.x1 && mouse.y2==w.y1 || mouse.x2==w.x2 && mouse.y2==w.y2);
}

bool canGo(wall mouse) {
 int cnt=0; // 쥐가 이동하면서 만나는 벽의 개수
 bool chk=false; // 구멍이 꼭짓점에 있는 경우
 for(int i=0;i<n;i++) {
 if(!crossChk(mouse, walls[i]) && !crossChk(walls[i], mouse)) {
 cnt++;
 }
 chk |= isCorner(mouse, walls[i]);
 }
 return (!chk && cnt==1 || chk && cnt==2); // 도착지점 한곳에서만 벽을 만나야함. (구멍이 꼭짓점에 있는 경우 벽 두개)
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> h >> m;

// 벽의 꼭짓점
 for(int i=0;i<n;i++) cin >> corner[i].x >> corner[i].y;

// 벽 위치 기록하기
 for(int i=0;i<n;i++) walls.push_back({corner[i].x, corner[i].y, corner[(i+1)%n].x, corner[(i+1)%n].y});

// 구멍 위치
 for(int i=0;i<h;i++) cin >> hole[i].x >> hole[i].y;

// 쥐 위치
 for(int i=0;i<m;i++) cin >> mouse[i].x >> mouse[i].y;

// S -> mouse 연결
 for(int i=0;i<m;i++) {
 conn[S].push_back(i);
 conn[i].push_back(S);
 c[S][i]=1;
 }

// mouse -> hole 연결
 for(int i=0;i<m;i++) {
 for(int j=0;j<h;j++) {
 if(canGo({mouse[i].x, mouse[i].y, hole[j].x, hole[j].y})) {
 conn[i].push_back(m+j);
 conn[m+j].push_back(i);
 c[i][m+j]=1;
 }
 }
 }

// hole -> E 연결
 for(int i=0;i<h;i++) {
 conn[m+i].push_back(E);
 conn[E].push_back(m+i);
 c[m+i][E]=k;
 }

// 에드몬드 카프
 int totalFlow=0;
 while(true) {
 queue<int> q; q.push(S);
 memset(prv, -1, sizeof prv);
 while(!q.empty() && prv[E]==-1) {
 int cur = q.front(); q.pop();
 for(int next:conn[cur]) {
 if(c[cur][next]-f[cur][next]>0 && prv[next]==-1) {
 prv[next]=cur;
 if(next==E) break;
 q.push(next);
 }
 }
 }
 if(prv[E]==-1) break;

for(int i=E;i!=S;i=prv[i]) {
 f[prv[i]][i]++;
 f[i][prv[i]]--;
 }
 totalFlow++;
 }
 if(totalFlow==m) cout << "Possible";
 else cout << "Impossible";
}
```