QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660533#2950. Growing Some Oobleckenze114514WA 0ms1900kbC++203.1kb2024-10-20 11:55:242024-10-20 11:55:24

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 11:55:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:1900kb
  • [2024-10-20 11:55:24]
  • 提交

answer

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

const double eps = 1e-8;
const double INF = 1e15;
const double pi = acos(-1.0);

struct node {
    double x, y, r, s;
    int del;
} a[120], b[120];

int n;

double dis(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}

double gettime() {
    double ret = INF;
    for (int i = 1; i <= n; i++) {
        if (a[i].del) continue;
        for (int j = i + 1; j <= n; j++) {
            if (a[j].del) continue;
            double dist = dis(a[i].x, a[i].y, a[j].x, a[j].y);
            double sum_r = a[i].r + a[j].r;
            double delta_r = a[i].s + a[j].s;
            if (delta_r == 0) continue; // Avoid division by zero
            double t = (dist - sum_r) / delta_r;
            if (t < ret) ret = t;
        }
    }
    return ret;
}

void expand(double t) {
    for (int i = 1; i <= n; i++) {
        if (!a[i].del) {
            a[i].r += t * a[i].s;
        }
    }
}

int touch(node x1, node x2) {
    double dist = dis(x1.x, x1.y, x2.x, x2.y);
    return dist <= x1.r + x2.r + eps;
}

void merge() {
    int fi = -1, fj = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i].del) continue;
        for (int j = i + 1; j <= n; j++) {
            if (a[j].del) continue;
            if (touch(a[i], a[j])) {
                fi = i;
                fj = j;
                break;
            }
        }
        if (fi != -1) break;
    }
    if (fi == -1) return; // No circles touch

    node now;
    now.x = (a[fi].x + a[fj].x);
    now.y = (a[fi].y + a[fj].y);
    double totalArea = pi * (a[fi].r * a[fi].r + a[fj].r * a[fj].r);
    double maxS = std::max(a[fi].s, a[fj].s);
    int cnt = 2;

    a[fi].del = 1;
    a[fj].del = 1;

    bool anyNewMerges = true;
    while (anyNewMerges) {
        anyNewMerges = false;
        for (int i = 1; i <= n; i++) {
            if (!a[i].del && touch(now, a[i])) {
                // Merge circle i into 'now'
                now.x += a[i].x;
                now.y += a[i].y;
                totalArea += pi * a[i].r * a[i].r;
                maxS = std::max(maxS, a[i].s);
                cnt++;
                a[i].del = 1;
                anyNewMerges = true;
            }
        }
    }

    now.x /= cnt;
    now.y /= cnt;
    now.r = sqrt(totalArea / pi);
    now.s = maxS;
    now.del = 0;

    int m = 1;
    b[m++] = now;
    for (int i = 1; i <= n; i++) {
        if (!a[i].del) {
            b[m++] = a[i];
        }
    }
    n = m - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = b[i];
        a[i].del = 0;
    }
}

void work() {
    while (n > 1) {
        double t = gettime();
        if (t == INF) break; 
        expand(t);
        merge();
    }
    if (n >= 1) {
        printf("%.10lf %.10lf\n", a[1].x, a[1].y);
        printf("%.10lf\n", a[1].r);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf%lf%lf", &a[i].x, &a[i].y, &a[i].r, &a[i].s);
        a[i].del = 0;
    }
    work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1900kb

input:

3
10 10 5 1
24 10 7 1
16 2 2 1

output:

16.5000000000 6.0000000000
7.5498344353

result:

wrong answer 3rd numbers differ - expected: '10.4403065', found: '7.5498344', error = '0.2768570'