oj.uz

Submission #233604

# Submission time Handle Problem Language Result Execution time Memory
233604 2020-05-21T05:03:02 Z cuom1999 Park (BOI16_park) C++14
100 / 100
 565 ms 105372 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

long 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;
    long double c;
    bool operator < (const Edge& e) {
        return c < e.c;
    }
};

long 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;
}

long 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;
                }
            }
        }
    }
    // cout << fixed << setprecision(5);
    // for (int i = 1; i <= 4; i++) {
    //     for (int j = i + 1; j <= 4; j++) {
    //         cout << i << " " << j << " " << minPath[i][j] << endl;
    //     }
    // }

    vector<vector<long double>> ans(5, vector<long 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 << ans[3][4] - 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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 105116 KB Output is correct
2 Correct 508 ms 105120 KB Output is correct
3 Correct 514 ms 105116 KB Output is correct
4 Correct 517 ms 105116 KB Output is correct
5 Correct 516 ms 105124 KB Output is correct
6 Correct 516 ms 105244 KB Output is correct
7 Correct 477 ms 105116 KB Output is correct
8 Correct 489 ms 105248 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2684 KB Output is correct
2 Correct 47 ms 2684 KB Output is correct
3 Correct 46 ms 2684 KB Output is correct
4 Correct 47 ms 2684 KB Output is correct
5 Correct 48 ms 2684 KB Output is correct
6 Correct 47 ms 2556 KB Output is correct
7 Correct 42 ms 760 KB Output is correct
8 Correct 42 ms 1912 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 105116 KB Output is correct
2 Correct 508 ms 105120 KB Output is correct
3 Correct 514 ms 105116 KB Output is correct
4 Correct 517 ms 105116 KB Output is correct
5 Correct 516 ms 105124 KB Output is correct
6 Correct 516 ms 105244 KB Output is correct
7 Correct 477 ms 105116 KB Output is correct
8 Correct 489 ms 105248 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 51 ms 2684 KB Output is correct
12 Correct 47 ms 2684 KB Output is correct
13 Correct 46 ms 2684 KB Output is correct
14 Correct 47 ms 2684 KB Output is correct
15 Correct 48 ms 2684 KB Output is correct
16 Correct 47 ms 2556 KB Output is correct
17 Correct 42 ms 760 KB Output is correct
18 Correct 42 ms 1912 KB Output is correct
19 Correct 557 ms 105372 KB Output is correct
20 Correct 550 ms 105372 KB Output is correct
21 Correct 565 ms 105372 KB Output is correct
22 Correct 553 ms 105372 KB Output is correct
23 Correct 563 ms 105372 KB Output is correct
24 Correct 532 ms 105372 KB Output is correct