BOJ 5449 - Farmer John 링크
(2023.05.09 기준 P4)

문제

소 Bessie의 위치와 음식의 위치가 2차원 평면 상의 점으로 주어진다. 그리고 N개의 울타리의 양 끝 점이 주어진다.
Bessie는 울타리는 넘지는 못하며 닿을 수는 있다고 하였을 때, 음식으로 가기 위한 최단 거리 출력

알고리즘

울타리에 걸리는 지는 선분 교차 판정 알고리즘으로 가려내고, 최단 거리는 다익스트라로 구한다.

풀이

점의 총 개수는 N * 2 + 2개다. N은 최대 100이며 Bessie와 음식의 거리만 구하면 되므로 다익스트라가 적당하다.

다익스트라를 이용하기 위해선 각 점마다의 거리를 구해야 한다.
이런 식으로 선분이 교차가 되지 않으면 거리를 구해주는 방식으로 그래프를 완성시켜 다익스트라를 돌리면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;

const int inf = INT_MAX;

double get_dist(pii a, pii b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

ll ccw(pii a, pii b, pii c){
    return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

bool is_intersect(pii a, pii b, pii c, pii d){
    ll ab = ccw(a, b, c) * ccw(a, b, d);
    ll cd = ccw(c, d, a) * ccw(c, d, b);
    // 일직선 상에서 포함하거나 겹치는 경우에도 선분이 교차하지 않는 것으로 판정
    return (ab < 0 && cd < 0);
}

void solve(){
    int Bx, By, Fx, Fy, N;
    cin >> Bx >> By >> Fx >> Fy >> N;

    vector<pii> points = {{Bx, By}, {Fx, Fy}};
    for (int i = 0, x1, y1, x2, y2; i < N; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        points.push_back({x1, y1});
        points.push_back({x2, y2});
    }

    N = N * 2 + 2; // 위치의 총 개수는 Bessie, Food, Fences * 2
    vector<pid> graph[N];
    // 모든 위치 쌍마다 울타리에 걸리지 않고 일직선으로 이동이 가능한지 확인
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++){
        bool possible = true;
        for (int k = 2; k < N; k += 2)
            if (is_intersect(points[i], points[j], points[k], points[k + 1])){
                possible = false;
                break;
            }
        if (possible){
            double d = get_dist(points[i], points[j]);
            graph[i].push_back({j, d});
            graph[j].push_back({i, d});
        }
    }

    // 다익스트라
    priority_queue<pdi, vector<pdi>, greater<pdi>> pq; pq.push({0, 0});
    vector<double> distance(N, inf); distance[0] = 0;
    while (!pq.empty()){
        auto [d, i] = pq.top(); pq.pop();
        if (distance[i] < d) continue;
        for (auto [j, dd]: graph[i])
            if (distance[j] > d + dd)
                distance[j] = d + dd, pq.push({distance[j], j});
    }

    cout << fixed << setprecision(6) << distance[1] << '\n';
}

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

    int T;
    cin >> T;
    while (T--) solve();
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush

def get_dist(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def ccw(a, b, c):
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0])

def is_intersect(a, b, c, d):
    ab = ccw(a, b, c) * ccw(a, b, d)
    cd = ccw(c, d, a) * ccw(c, d, b)
    # 일직선 상에서 포함하거나 겹치는 경우에도 선분이 교차하지 않는 것으로 판정
    return ab < 0 and cd < 0

for _ in range(int(input())):
    Bx, By, Fx, Fy = map(int, input().split())
    points = [(Bx, By), (Fx, Fy)]

    N = int(input())
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        points.append((x1, y1))
        points.append((x2, y2))

    N = N * 2 + 2 # 위치의 총 개수는 Bessie, Food, Fences * 2
    graph = [[] for _ in range(N)]

    # 모든 위치 쌍마다 울타리에 걸리지 않고 일직선으로 이동이 가능한지 확인
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(2, N, 2):
                if is_intersect(points[i], points[j], points[k], points[k + 1]):
                    break
            else:
                d = get_dist(points[i], points[j])
                graph[i].append((j, d))
                graph[j].append((i, d))

    # 다익스트라
    queue = [(0, 0)]
    distance = [inf] * N
    distance[0] = 0
    while queue:
        d, i = heappop(queue)
        if distance[i] < d:
            continue
        for j, dd in graph[i]:
            if distance[j] > d + dd:
                distance[j] = d + dd
                heappush(queue, (distance[j], j))

    print(format(distance[1], '.6f'))