[BOJ 14750] Jerry and Tom

문제

---

https://www.acmicpc.net/problem/14750

풀이

---

ICPC 2017 한국 예선 E번 문제

문제도 직관적이고 풀이도 떠올리기 쉬운 편이다.

각 구멍에 최대 K마리의 쥐가 숨을 수 있고, 어떤 구멍에 쥐가 숨을 수 있으려면 구멍-쥐 선분이 벽과 만나면 안된다.

최대 K마리라는 조건에서 최대 유량을 떠올리고, flow network의 엣지는 선분 교차 판정으로 결정해주면 된다.

벽의 수는 최대 1000, 구멍의 수는 최대 50, 그리고 쥐의 수는 최대 250이므로 1000 * 50 * 250 = 12500000.

모든 선분 쌍에 대해 교차 판정을 해줘도 된다.

C++로 풀 때, ccw 계산 과정 중 int 범위를 벗어날 수 있으므로 long long으로 계산해야 한다.

코드

---

#include <iostream>
#include <utility>
#include <deque>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

int ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
    long long res = (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1);
    if (res > 0) return 1;
    if (res < 0) return -1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n, k, h, m, x, y;
    cin >> n >> k >> h >> m;
    pii house[n], hide[h], mouse[m];

    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        house[i] = pii(x, y);
    }
    for (int i = 0; i < h; i++) {
        cin >> x >> y;
        hide[i] = pii(x, y);
    }
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        mouse[i] = pii(x, y);
    }

    int graph[h + m + 2][h + m + 2];
    memset(graph, 0, sizeof(graph));

    for (int i = 1; i < h + 1; i++) {
        graph[0][i] = k;
    }
    for (int i = h + 1; i < h + m + 1; i++) {
        graph[i][h + m + 1] = 1;
    }
    for (int i = 0; i < h; i++) {
        int hx = hide[i].first;
        int hy = hide[i].second;
        for (int j = 0; j < m; j++) {
            int mx = mouse[j].first;
            int my = mouse[j].second;
            bool flag = true;

            for (int p = 0; p < n; p++) {
                int x1 = house[p].first;
                int y1 = house[p].second;
                int x2 = house[(p + 1) % n].first;
                int y2 = house[(p + 1) % n].second;
                
                if (ccw(x1, y1, hx, hy, x2, y2) == 0) continue;
                if (ccw(x1, y1, x2, y2, hx, hy) * ccw(x1, y1, x2, y2, mx, my) > 0) continue;
                if (ccw(hx, hy, mx, my, x1, y1) * ccw(hx, hy, mx, my, x2, y2) > 0) continue;
                flag = false;
                break;
            }
            if (flag) {
                graph[i + 1][h + j + 1] = 1;
            }
        }
    }
    int ans = 0, res, nxt;
    while (true) {
        int prev[h + m + 2];
        fill_n(prev, h + m + 2, -1);

        deque<pii> queue;
        queue.push_back(pii(0, k + 1));

        while (!queue.empty()) {
            int cur = queue.front().first;
            res = queue.front().second;
            queue.pop_front();

            if (graph[cur][h + m + 1]) {
                res = min(res, graph[cur][h + m + 1]);
                prev[h + m + 1] = cur;
                break;
            }
            for (nxt = 1; nxt < h + m + 1; nxt++) {
                if (prev[nxt] == -1 && graph[cur][nxt]) {
                    prev[nxt] = cur;
                    queue.push_back(pii(nxt, min(res, graph[cur][nxt])));
                }
            }
            if (prev[h + m + 1] != -1) break;
        }
        if (prev[h + m + 1] == -1) break;

        ans += res;
        nxt = h + m + 1;
        while (true) {
            int cur = prev[nxt];
            graph[cur][nxt] -= res;
            graph[nxt][cur] += res;
            nxt = cur;
            if (nxt == 0) break;
        }
    }
    if (ans == m) cout << "Possible";
    else cout << "Impossible";
}

import sys
from collections import deque


def ccw(x1, y1, x2, y2, x3, y3):
    return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1)


n, k, h, m = map(int, sys.stdin.readline().split())
house = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
hide = [tuple(map(int, sys.stdin.readline().split())) for _ in range(h)]
mouse = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
graph = [[0] * (h + m + 2) for _ in range(h + m + 2)]

for i in range(1, h + 1):
    graph[0][i] = k

for i in range(h + 1, h + m + 1):
    graph[i][h + m + 1] = 1

for i in range(h):
    hx, hy = hide[i]

    for j in range(m):
        mx, my = mouse[j]
        flag = True

        for p in range(n):
            x1, y1 = house[p]
            x2, y2 = house[(p + 1) % n]

            if (ccw(x1, y1, hx, hy, x2, y2) == 0) or (ccw(x1, y1, x2, y2, hx, hy) * ccw(x1, y1, x2, y2, mx, my) > 0) or (ccw(hx, hy, mx, my, x1, y1) * ccw(hx, hy, mx, my, x2, y2) > 0):
                continue
            
            flag = False
            break

        if flag:
            graph[i + 1][h +j + 1] = 1

ans = 0
while True:
    prev = [-1] * (h + m + 2)
    queue = deque([(0, float('inf'))])
    while queue:
        cur, res = queue.popleft()
        
        if graph[cur][-1]:
            res = min(res, graph[cur][-1])
            prev[-1] = cur
            break
        
        for nxt in range(1, h + m + 1):
            if (prev[nxt] == -1) and graph[cur][nxt]:
                prev[nxt] = cur
                queue.append((nxt, min(res, graph[cur][nxt])))

        if prev[-1] != -1:
            break
    
    if prev[-1] == -1:
        break

    ans += res
    nxt = -1
    while True:
        cur = prev[nxt]
        graph[cur][nxt] -= res
        graph[nxt][cur] += res
        nxt = cur
        if nxt == 0:
            break

if ans == m:
    print('Possible')
else:
    print('Impossible')