Problem Solution

1 solutions

  • 0
    @ 2024-11-05 23:27:32
    #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() ;
    }
    
    
  • 1

Information

ID
1123
Difficulty
8
Category
Geometry Click to Show
Tags
# Submissions
32
Accepted
4
Accepted Ratio
12%
Uploaded By