Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: bradyawn
- PROG: contest
- LANG: C++11
- */
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <deque>
- #include <string>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <utility>
- #include <set>
- #include <unordered_set>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <bitset>
- #include <random>
- #include <cstring>
- #include <complex>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> i2;
- typedef pair<ll,ll> ll2;
- int n;
- int x[100001];
- int y[100001];
- //1e5 * 30 * 30
- const int LOGMAX = 40;
- const double EPS = 1e-7;
- bool f(double r, double p)
- {
- ld ret = 0;
- for (int i = 1; i <= n; i++)
- {
- ld dx = p-x[i];
- ld dy = r-y[i];
- ret = max(ret, dx*dx + dy*dy);
- }
- return ret < (ld)r*r; //farthest squared distance
- }
- int mx = 0;
- double ans = 1e18;
- bool ok = false;
- int hits = 0;
- double calc(double p) //minimum radius needed to work loc p
- {
- double lo = 0;
- double hi = (double)mx * mx;
- for (int i = 1; i <= LOGMAX; i++)
- {
- double mid = (lo+hi)/2;
- if (f(mid, p)) {hi = mid; ans = min(ans, mid); }
- else lo = mid;
- }
- return lo;
- }
- int main()
- {
- //ifstream inf("");
- //ofstream outf("");
- cout << setprecision(15);
- ios::sync_with_stdio(0); cin.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++)
- {
- cin >> x[i] >> y[i];
- if (y[i] < 0) hits++;
- mx = max(mx, y[i]);
- mx = max(mx, x[i]);
- }
- if (hits > 0) for (int i = 1; i <= n; i++) {x[i] *= -1; y[i] *= -1;}
- if (hits != n && hits != 0) {cout << -1 << '\n'; return 0;}
- double lo = -2*mx;
- double hi = 2*mx;
- for (int i = 1; i <= LOGMAX; i++)
- {
- double lm = lo + (hi - lo)/3;
- double rm = hi - (hi - lo)/3;
- if (calc(lm) < calc(rm)) hi = rm;
- else lo = lm;
- }
- cout << calc(lo) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement