제출 #233960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233960		anhkha2003	Park (BOI16_park)	C++14	100 / 100	699 ms	104020 KiB

park

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

const long double EPS = 1e-8;

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

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

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

long long w, h;
long double distEdge(Circle a, int k) {
    if (k == 1) return a.y - a.r;
    if (k == 2) return w - a.x - a.r;
    if (k == 3) return h - a.y - a.r;
    return a.x - a.r;
}

struct Edge {
    long long u, v;
    long double w;
};

bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int root[2005];

int findRoot(int u) {
    while (root[u] >= 0) {
        u = root[u];
    }
    return u;
}

void join(int x, int y) {
    if (root[x] > root[y]) {
        swap(x, y);
    }
    root[x] += root[y];
    root[y] = x;
}

Circle circle[2005];
long double cost[2005][2005];
long double green[5][5];
long double ans[5][5];

int main() {
    //freopen("PARK.INP", "r", stdin);
   // freopen("PARK.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m >> w >> h;

    for (int i = 1; i <= n; i++) {
        cin >> circle[i].x >> circle[i].y >> circle[i].r;
    }

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

        for (int j = 1; j <= 4; j++) {
            cost[i][n + j] = distEdge(circle[i], j);
            edges.push_back({i, n + j, cost[i][n + j]});
        }
    }

    sort(edges.begin(), edges.end(), cmp);

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

    for (auto &e: edges) {
        int x = findRoot(e.u);
        int y = findRoot(e.v);
        if (x == y) continue;

        join(x, y);

        for (int i = 1; i <= 4; i++) {
            for (int j = i + 1; j <= 4; j++) {
                if (findRoot(n + i) == findRoot(n + j) && green[i][j] == -1) {
                    green[i][j] = e.w;
                }
            }
        }
    }

    // 1 -> 2: 1-2, 1-3, 1-4
    // 1 -> 3: 1-4, 1-3, 2-3, 2-4
    // 1 -> 4: 1-4, 2-4, 3-4
    // 2 -> 3: 1-2, 2-4, 2-3
    // 2 -> 4: 1-2, 3-4, 1-3, 2-4
    // 3 -> 4: 2-3, 1-3, 3-4

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

    for (int i = 1; i <= m; i++) {
        int r, e;
        cin >> r >> e;

        for (int j = 1; j <= 4; j++) {
            if (e == j) ans[e][j] = 2e9;
            if (2 * r <= ans[e][j] + EPS) {
                cout << j;
            }
        }
        cout << "\n";
    }

    return 0;
}

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