제출 #233602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233602		cuom1999	Park (BOI16_park)	C++14	0 / 100	349 ms	56284 KiB

park

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

struct Circle {
    long long x, y, r;
};

double sq(double a) {
    return a * a;
}

double dist(Circle a, Circle b) {
    return sqrt(sq(a.x - b.x) + sq(a.y - b.y)) - a.r - b.r;
}

struct Edge {
    int x, y;
    double c;
    bool operator < (const Edge& e) {
        return c < e.c;
    }
};

double cost[2005][2005];
Circle circle[2005];

int lab[2005];
int getRoot(int a) {
    if (lab[a] < 0) return a;
    return lab[a] = getRoot(lab[a]);
}

void dsu(int a, int b) {
    if (lab[a] > lab[b]) swap(a, b);
    lab[a] += lab[b];
    lab[b] = a;
}

double minPath[5][5];

// #include "geodeb.h"

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m;
    long long w, h;

    // GD_INIT("geo.html");
    cin >> n >> m >> w >> h;
    // GD_SEGMENT(0, 0, w, 0, "black");
    // GD_SEGMENT(0, 0, 0, h, "black");
    // GD_SEGMENT(w, 0, w, h, "black");
    // GD_SEGMENT(0, h, w, h, "black");
    
    for (int i = 1; i <= n; i++) {
        cin >> circle[i].x >> circle[i].y >> circle[i].r;
        // GD_CIRCLE(circle[i].x, circle[i].y, circle[i].r, "blue");
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cost[i][j] = dist(circle[i], circle[j]);
        }

        cost[i][n + 1] = circle[i].y - circle[i].r;
        cost[i][n + 2] = w - circle[i].x - circle[i].r;
        cost[i][n + 3] = h - circle[i].y - circle[i].r;
        cost[i][n + 4] = circle[i].x - circle[i].r;
    }

    vector<Edge> edges;
    for (int i = 1; i <= n + 4; i++) {
        for (int j = i + 1; j <= n + 4; j++) {
            if (i > n && j > n) cost[i][j] = 1e9;
            edges.push_back({i, j, cost[i][j]});
        }
    }

    for (int i = 1; i <= 4; i++) {
        for (int j = i + 1; j <= 4; j++) {
            minPath[i][j] = -1;
        }
    }

    memset(lab, -1, sizeof(lab));
    sort(edges.begin(), edges.end());

    for (auto &e: edges) {
        // cout << e.x << " " << e.y << " " << e.c << endl;
        int a = getRoot(e.x);
        int b = getRoot(e.y);
        if (a == b) continue;
        dsu(a, b);
        // cout << e.x << " " << e.y << " " << e.c << endl;
        // if (max(e.x, e.y) > n) cout << e.x << " " << e.y << " " << e.c << endl;
        for (int i = n + 1; i <= n + 4; i++) {
            for (int j = i + 1; j <= n + 4; j++) {
                if (minPath[i - n][j - n] == -1 && getRoot(i) == getRoot(j)) {
                    minPath[i - n][j - n] = minPath[j - n][i - n] = e.c;
                }
            }
        }
    }

    // for (int i = 1; i <= 4; i++) {
    //     for (int j = i + 1; j <= 4; j++) {
    //         cout << i << " " << j << " " << minPath[i][j] << endl;
    //     }
    // }

    vector<vector<double>> ans(5, vector<double>(5, 1e9));

    for (int i = 1; i <= 4; i++) {
        int j = i + 1;
        if (i == 4) j = 1;
        for (int k = 1; k <= 4; k++) {
            if (k != i) ans[i][j] = min(ans[i][j], minPath[i][k]);
        }
        ans[j][i] = ans[i][j];
    }    

    ans[1][3] = ans[3][1] = min({minPath[1][3], minPath[2][4], 
                                minPath[1][4], minPath[2][3]});

    ans[2][4] = ans[4][2] = min({minPath[1][3], minPath[2][4], 
                                minPath[1][2], minPath[3][4]});

        
    for (int i = 1; i <= m; i++) {
        int r, e;
        cin >> r >> e;
        // cout << r * 2 << endl;
        // GD_CIRCLE(r, r, r, "red");
        for (int j = 1; j <= 4; j++) {
            if (ans[e][j] + 1e-8 >= r * 2) {
                cout << j;
            }
        }
        cout << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42