/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 340.0 KiB
#2 Accepted 2ms 328.0 KiB
#3 Accepted 2ms 540.0 KiB
#4 Wrong Answer 6ms 540.0 KiB
#5 Accepted 6ms 548.0 KiB
#6 Accepted 6ms 548.0 KiB
#7 Accepted 5ms 548.0 KiB
#8 Wrong Answer 2ms 328.0 KiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
using ld = long double;
int n;
vector<pair<ld,ld>> v(101);
ld ep = 0.0000001L;

bool check(ld x,ld y,ld r)
{
    ld dis;
    for(int i=0;i<n;i++)
    {
        dis = sqrtl((v[i].first-x)*(v[i].first-x) + (v[i].second-y)*(v[i].second-y));
        if(dis - r > ep) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++) cin >> v[i].first >> v[i].second;

    ld ans = 1e9,xm,ym,d,x,y,m;

    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            xm = (v[i].first + v[j].first)/2.0L;
            ym = (v[i].second + v[j].second)/2.0L;
            if(v[i].first == v[j].first) m = 0;
            else if(v[i].second==v[j].second ) m = INFINITY;
            else m = ((v[i].second-v[j].second) / (v[i].first - v[j].first)) * (-1);

            d = sqrtl((v[i].first-xm)*(v[i].first-xm) + (v[i].second-ym)*(v[i].second-ym));
            ld lo=d+ep,hi=20000,mid,R=1e9,D;
            while(hi-lo > ep)
            {
                mid = (lo+hi)/2.0L;
                D = sqrtl(mid*mid - d*d);
                if(m==INFINITY)
                {
                    x = xm;
                    y = ym+D;
                }
                else 
                {
                    x = xm + (D / sqrtl(1+(m*m)));
                    y = ym + (D*m / sqrtl(1+m*m));
                }
                

                if(check(x,y,mid))
                {
                    R = mid;
                    hi = mid-ep;
                }
                else lo = mid+ep;
            }
            ans = min(ans,R);
            lo=d+ep, hi=20000, R=1e9;
            while(hi-lo > ep)
            {
                mid = (lo+hi)/2.0L;
                D = sqrtl(mid*mid - d*d);
                if(m==INFINITY)
                {
                    x = xm;
                    y = ym-D;
                }
                else 
                {
                    x = xm - (D / sqrtl(1+m*m));
                    y = ym - (D*m / sqrtl(1+m*m));
                }
                
                if(check(x,y,mid))
                {
                    R = mid;
                    hi = mid-ep;
                }
                else lo = mid+ep;
            }
            ans = min(ans , R);
            if(check(v[i].first,v[i].second,d)) ans = min(ans , d);
            if(check(v[j].first,v[j].second,d)) ans = min(ans , d);
            //cout<<ans<<endl;
        }
    }

    cout<<fixed<<setprecision(15)<<ans<<endl;
}

Information

Submit By
Type
Submission
Problem
P1123 Relic Rescue Radius!
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-03 15:42:15
Judged At
2024-11-11 02:34:00
Judged By
Score
30
Total Time
6ms
Peak Memory
548.0 KiB