1 solutions
-
0_MJiH_ LV 4 MOD @ 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