QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660475#2950. Growing Some Oobleckenze114514WA 0ms3864kbC++2010.3kb2024-10-20 11:27:062024-10-20 11:27:06

Judging History

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

  • [2024-10-20 11:27:06]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3864kb
  • [2024-10-20 11:27:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;
const ll INF = 1e18;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

template<typename T>
struct Point{
    T x, y;
    ld eps;

    Point() : x(0), y(0), eps(1e-9) {}
    Point(T x, T y) : x(x), y(y), eps(1e-9) {}

    void set_eps(T eps){
        this->eps = eps;
    }

    Point operator+ (const Point& b){
        return Point(x + b.x, y + b.y);
    }

    Point operator- (const Point& b){
        return Point(x - b.x, y - b.y);
    }

    Point operator- (){
        return Point(-x, -y);
    }

    Point operator* (T t) const{
        return Point(x * t, y * t);
    }

    Point operator/ (T t) const{
        return Point(x / t, y / t);
    }

    Point &operator+=(Point p) &{
        x += p.x;
        y += p.y;
        return *this;
    }

    Point &operator-=(Point p) &{
        x -= p.x;
        y -= p.y;
        return *this;
    }

    Point &operator*=(T v) &{
        x *= v;
        y *= v;
        return *this;
    }

    Point &operator/=(T v) &{
        x /= v;
        y /= v;
        return *this;
    }

    Point &operator=(const Point& b) &{
        x = b.x;
        y = b.y;
        return *this;
    }

    friend Point operator+ (const Point& a, const Point& b){
        return {a.x + b.x, a.y + b.y};
    }

    friend Point operator- (const Point& a, const Point& b){
        return {a.x - b.x, a.y - b.y};
    }

    friend bool operator==(Point a, Point b){
        return a.x == b.x && a.y == b.y;
    }

    int sign(T x){
        if(fabs(x) < eps){
            return 0;
        }
        if(x < 0){
            return -1;
        }
        return 1;
    }

    bool cmp(T x, T y){
        if(fabs(x - y) > eps){
            return 0;
        }
        return 1;
    }

    bool cmp(const Point& a, const Point& b){
        return cmp(a.x, b.x) && cmp(a.y, b.y);
    }

    T dot(const Point& a, const Point& b){
        return a.x * b.x + a.y * b.y;
    }

    T square(Point a){
        return dot(a, a);
    }

    T cross(const Point& a, const Point& b){
        return a.x * b.y - a.y * b.x;
    }

    T cross(const Point& a, const Point& b, const Point& p){
        return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    }

    T get_len(const Point& a){
        return sqrt(dot(a, a));
    }

    T get_angle(const Point& a, const Point& b){
        return acos(dot(a, b) / get_len(a) / get_len(b));
    }

    T area(const Point& a, const Point& b, const Point& c){
        return cross(b - a, c - a);
    }

    Point rotate(const Point& a, T angle){ //两个点就 b - a (b按a转)
        T dx = a.x * cos(angle) + a.y * sin(angle); 
        T dy = -a.x * sin(angle) + a.y * cos(angle);
        return Point(dx, dy);
    }

    Point intersect(const Point& p, const Point& v, const Point& q, const Point& w){
        Point u = p - q;
        T t = cross(w, u) / cross(v, w);
        return p + v * t;
    }

    T point_dist(const Point& a, const Point& b){
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }

    T line_dist(const Point& a, const Point& b, const Point& p){
        Point u = b - a, v = p - a;
        return fabs(cross(u, v)) / get_len(u);
    }

    T get_slope(const Point& a, const Point& b){
        if(b.y == a.y) return INF;
        if(b.x == a.x) return 0;
        return (b.y - a.y) / (b.x - a.x);
    }

    T circle_intersect(const Point& p1, const Point& p2, const T r1, const T r2){
        ld d = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));

        if(d > r1 + r2 || d + chmin(r1, r2) <= chmax(r1, r2)){
            return 0;
        }
        else if(d == r1 + r2){
            return 1;
        }
        else{
            return 2;
        }
    }

    T seg_dist(const Point& a, const Point& b, const Point& p){
        if(a == b){
            return get_len(p - a);
        }
        Point u = b - a, v = p - a, w = p - b;

        if(sign(dot(u, v)) < 0){
            return get_len(v);
        }
        if(sign(dot(u, w)) > 0){
            return get_len(w);
        }
        return line_dist(a, b, p);
    }

    Point projection(const Point& a, const Point& b, const Point& p){
        Point v = b - a;
        return a + v * dot(v, p - a) / get_len(v);
    }

    bool on_segment(const Point& a, const Point& b, const Point& p){
        bool u = sign(cross(p - a, p - b)) == 0;
        bool v = sign(dot(p - a, p - b)) <= 0;
        return u && v;
    }

    bool seg_intersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2){
        T c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
        T c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
        return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
    }

    vector<Point> get_circle_intersection(const Point& p1, const Point& p2, const T r1, const T r2){
        ld d = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));

        Point bv = {(p2.x - p1.x) / d, (p2.y - p1.y) / d};

        if(d >= r1 + r2){
            return {};
        }
        else if(d + chmin(r1, r2) <= chmax(r1, r2)){
            return {{INF, INF}};
        }
        else{
            Point<T> center;
            ld a = (r1 * r1 - r2 * r2 + d * d) / (2 * d);
            ld b = (r2 * r2 - r1 * r1 + d * d) / (2 * d);

            center.x = p1.x + a * bv.x;
            center.y = p1.y + a * bv.y;

            ld h = sqrt(r1 * r1 - a * a);
            Point it1 = {center.x + h * bv.y, center.y - h * bv.x};
            Point it2 = {center.x - h * bv.y, center.y + h * bv.x};

            return {it1, it2};
        }
    }

    ld circle_rad(const T r1, const T r2){
        return sqrt(r1 * r1 + r2 * r2);
    }
};

const int N = (int)1e3 + 1, M = N * 2;
int vis[N], n;

void dfs(vector<ld> &p, vector<vector<ld>> &a){
    while (true) {
        if (all_of(vis, vis + n, [](int v){ return v; })) {
            return;
        }

        ld min_t = INF;
        for(int i = 0; i < n; i++){
            if(vis[i]) continue;

            ld x = a[i][0], y = a[i][1], r = a[i][2];
            Point<ld> p1 = {x, y}, p2 = {p[0], p[1]};
            ld dist = p1.point_dist(p1, p2);
            ld sum_r = r + p[2];
            if(dist <= sum_r){
                min_t = 0;
                break;
            } 
            else {
                ld delta_r = a[i][3] + p[3];
                ld time_to_touch = (dist - sum_r) / delta_r;
                if(time_to_touch < min_t){
                    min_t = time_to_touch;
                }
            }
        }

        for(int i = 0; i < n; i++){
            if(!vis[i]){
                a[i][2] += a[i][3] * min_t;
            }
        }
        p[2] += p[3] * min_t;

        if(min_t == INF){
            return;
        }

        bool anyNewMerges = true;
        while(anyNewMerges){
            anyNewMerges = false;
            vector<int> mergedCircles;
            for(int i = 0; i < n; i++){
                if(!vis[i]){
                    ld x = a[i][0], y = a[i][1], r = a[i][2];
                    Point<ld> p1 = {x, y}, p2 = {p[0], p[1]};
                    ld dist = p1.point_dist(p1, p2);
                    ld sum_r = r + p[2];
                    if(dist <= sum_r){
                        vis[i] = 1;
                        mergedCircles.push_back(i);
                        anyNewMerges = true;
                    }
                }
            }
            if(anyNewMerges){
                int count = 1 + mergedCircles.size();
                ld sumX = p[0], sumY = p[1];
                ld totalArea = p[2] * p[2] * pi;
                ld maxS = p[3];
                for(int idx : mergedCircles){
                    ld x = a[idx][0], y = a[idx][1], r = a[idx][2], s = a[idx][3];
                    sumX += x;
                    sumY += y;
                    totalArea += r * r * pi;
                    maxS = max(maxS, s);
                }
                p[0] = sumX / count;
                p[1] = sumY / count;
                p[2] = sqrt(totalArea / pi);
                p[3] = maxS;
            }
        }
    }
}

void solve() {
    cin >> n;

    vector<vector<ld>> a(n, vector<ld>(4));
    for(int i = 0; i < n; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    }

    ld min_t = INF;
    int id1 = -1, id2 = -1;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            ld x1 = a[i][0], y1 = a[i][1], r1 = a[i][2];
            ld x2 = a[j][0], y2 = a[j][1], r2 = a[j][2];
            Point<ld> p1 = {x1, y1}, p2 = {x2, y2};
            ld dist = p1.point_dist(p1, p2);
            ld sum_r = r1 + r2;
            if(dist <= sum_r){
                ld time_to_touch = 0;
                if(time_to_touch < min_t){
                    min_t = time_to_touch;
                    id1 = i;
                    id2 = j;
                }
            } else {
                ld delta_r = a[i][3] + a[j][3];
                ld time_to_touch = (dist - sum_r) / delta_r;
                if(time_to_touch < min_t){
                    min_t = time_to_touch;
                    id1 = i;
                    id2 = j;
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        a[i][2] += a[i][3] * min_t;
    }

    memset(vis, 0, sizeof(vis));
    vis[id1] = vis[id2] = 1;

    ld dx = (a[id1][0] + a[id2][0]) / 2;
    ld dy = (a[id1][1] + a[id2][1]) / 2;
    ld area = a[id1][2] * a[id1][2] * pi + a[id2][2] * a[id2][2] * pi;
    ld r = sqrt(area / pi);
    ld s = max(a[id1][3], a[id2][3]);

    vector<ld> p = {dx, dy, r, s};
    dfs(p, a);

    cout << setprecision(20) << fixed << p[0] << " " << p[1] << endl;
    cout << setprecision(20) << fixed << p[2] << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3864kb

input:

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

output:

16.50000000000000000000 6.00000000000000000000
10.44030650891055017962

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

5
-5 0 1 1
6 0 1 1
0 7 1 1
0 -8 1 1
0 0 1 2

output:

1.18750000000000000000 -3.12500000000000000000
7.61677681312230480315

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

2
-1000000000 0 1 1
1000000000 0 1 1

output:

0.00000000000000000000 0.00000000000000000000
1414213562.37309504882432520390

result:

ok 3 numbers

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3768kb

input:

4
-100000000 -1000000000 1 2
1000000000 -1000000000 1 2
-1000000000 1000000000 1 3
1000000000 1000000000 1 3

output:

-137500000.00000000000000000000 500000000.00000000000000000000
1840816448.24323888751678168774

result:

wrong answer 1st numbers differ - expected: '225000000.0000000', found: '-137500000.0000000', error = '1.6111111'