/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 496.0 KiB
#2 Accepted 3ms 512.0 KiB
#3 Accepted 2ms 508.0 KiB
#4 Accepted 2ms 480.0 KiB
#5 Accepted 2ms 492.0 KiB
#6 Accepted 2ms 512.0 KiB
#7 Accepted 2ms 328.0 KiB
#8 Accepted 3ms 516.0 KiB
#9 Accepted 2ms 516.0 KiB
#10 Accepted 2ms 488.0 KiB
#11 Accepted 3ms 484.0 KiB
#12 Accepted 2ms 500.0 KiB
#13 Accepted 2ms 488.0 KiB
#14 Accepted 2ms 616.0 KiB
#15 Accepted 2ms 328.0 KiB
#16 Accepted 2ms 432.0 KiB
#17 Accepted 2ms 332.0 KiB
#18 Accepted 2ms 480.0 KiB
#19 Accepted 2ms 328.0 KiB
#20 Accepted 2ms 492.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll>                   PII;
const double eps = 1e-12;
struct node
{
	double x, y;
}a[ 500010 ];
node o;
int n;
double r;
double dis( node a, node b )
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
void make( node p1, node p2, node p3 )
{
	double a, b, c, d, e, f;
	a = p2.y - p1.y;
	b = p3.y - p1.y;
	c = p2.x - p1.x;
	d = p3.x - p1.x;
	f = p3.x * p3.x + p3.y * p3.y - p1.x * p1.x - p1.y * p1.y;
	e = p2.x * p2.x + p2.y * p2.y - p1.x * p1.x - p1.y * p1.y;
	o.x = ( a * f - b * e ) / ( 2 * a * d - 2 * b * c );
	o.y = ( d * e - c * f ) / ( 2 * a * d - 2 * b * c );
	r = dis( o, p1 );
}
void solve()
{
    int n ; cin >> n ;
    for(int i = 1 ; i <= n ; i++) cin >> a[i].x >>  a[i].y ;
    random_shuffle(a + 1, a + n + 1);
    o = a[ 1 ]; r = 0;
    for(int i = 2; i <= n; i++) {
        if(dis( a[ i ], o ) > r + eps) {
            o = a[ i ], r = 0;
            for(int j = 1; j <= i - 1; j++) {
                if(dis( o, a[ j ] ) > r + eps) {
                    o.x = ( a[ i ].x + a[ j ].x ) / 2;
                    o.y = ( a[ i ].y + a[ j ].y ) / 2;
                    r = dis( o, a[ j ] );
                    for(int k = 1; k <= j - 1; k++) {
                        if(dis( o, a[ k ] ) > r + eps) make(a[i], a[j], a[k] );
                    }
                }
            }
        }
    }
    cout <<setprecision(20) << r << "\n";

}
int main()
{
     __Heart__
   //  READ("input18.txt") ;
    // WRITE("output18.txt") ;
     int t ; t = 1 ; while(t--) solve() ;
}

Information

Submit By
Type
Submission
Problem
P1123 Relic Rescue Radius!
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-29 00:43:21
Judged At
2024-11-11 02:35:59
Judged By
Score
100
Total Time
3ms
Peak Memory
616.0 KiB