AGC 019 C

시작점에서 도착점까지 최단 경로를 구할 때 가로와 세로 중 한 방향을 먼저 끝까지 이동한 뒤 다른 방향으로 이동해도 거리는 손실되지 않는다. 도로 간격이 모두 동일하고 분수대가 교차점에만 존재하므로, 최단 경로는 결국 ‘ㄱ’자 형태로 압축될 수 있기 때문이다. 이렇게 한 방향을 먼저 확정한 뒤에는 시작점과 도착점이 만드는 직사각형 내부에 있는 분수대만 신경 쓰면 된다. 분수대는 같은 가로나 같은 세로에 두 개 이상 존재하지 않으므로, 직사각형 내부 분수대를 x 좌표 기준으로 정렬했을 때 y 좌표가 증가하는 부분수열, 즉 LIS를 구하면 우회 가능한 분수대의 최소 개수를 알 수 있다.

 

분수대 하나를 우회할 때 차량은 직선 20미터를 달릴 대신 반지름 10미터짜리 4분의 1원호를 따라 이동한다. 원호 길이가 5π이므로 우회 한 번마다 추가 거리는 5π − 20미터가 된다. 가로 이동 거리와 세로 이동 거리 중 더 짧은 축보다 분수대가 하나 많을 때는 꼭짓점에서 반원을 한 번 더 돌아야 최단이 되는데, 이때 5π를 한 번 더 더해 주면 된다. 결국 최단 거리는 기본 맨해튼 거리(|Δx| + |Δy|) × 100에 필수 우회 k회에 대한 $k × (5π − 20)$을 더하고, 특수 상황이면 5π를 추가한 값이 된다.

 

알고리즘은 먼저 입력 좌표를 받아 시작점과 도착점의 y 좌표가 증가하도록 재배열한다. 이후 직사각형 내부 분수대만 필터링한 뒤 진행 방향에 맞춰 x 오름차순 혹은 내림차순으로 정렬하고, y 좌표에 대해 이분 탐색을 이용해 LIS 길이를 구한다. 전체 과정은 정렬과 LIS 단계에서 $O(N log N)$ 시간이 걸리고, 메모리는 분수대 정보를 저장하는 $O(N)$ 정도만 필요하다.

 

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

using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using qll = tuple<ll, ll, ll, ll>;
using ld = long double;

constexpr ll MAX = 1 << 19;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1LL << 61;
constexpr ll dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
const ld PI = acos(-1.);

inline void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(15);
}

int main(){
    init();

    ll a, b, c, d, n;

    cin >> a >> b >> c >> d >> n;

    vector<pll> p;

    if (b > d) {
        swap(a, c);
        swap(b, d);
    }

    for (ll x, y, i = 0; i < n; i++) {
        cin >> x >> y;

        if (min(a, c) <= x and x <= max(a, c) and min(b, d) <= y and y <= max(b, d)) {
            p.emplace_back(x, y);
        }
    }

    if (a > c) {
        sort(p.rbegin(), p.rend());
    } else {
        sort(p.begin(), p.end());
    }

    vector<ll> v;

    for (auto& [x, y] : p) {
        if (v.empty() or v.back() < y) {
            v.emplace_back(y);
        } else {
            *lower_bound(v.begin(), v.end(), y) = y;
        }
    }

    ld ans = (ld(abs(a - c)) + ld(abs(b - d))) * 100;
    ans += (5 * PI - 20) * ld(v.size());

    if (v.size() == min(abs(a - c), abs(b - d)) + 1) {
        ans += 5 * PI;
    }

    cout << ans;

    return 0;
}