Advertisement
Guest User

Untitled

a guest
Oct 10th, 2018
256
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None
  1. /*
  2.  ID: bradyawn
  3.  PROG: contest
  4.  LANG: C++11
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <vector>
  12. #include <deque>
  13. #include <string>
  14. #include <cmath>
  15. #include <map>
  16. #include <unordered_map>
  17. #include <utility>
  18. #include <set>
  19. #include <unordered_set>
  20. #include <ctime>
  21. #include <queue>
  22. #include <stack>
  23. #include <bitset>
  24. #include <random>
  25. #include <cstring>
  26. #include <complex>
  27. #include <cassert>
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32. typedef long double ld;
  33. typedef pair<int,int> i2;
  34. typedef pair<ll,ll> ll2;
  35.  
  36. int n;
  37.  
  38. int x[100001];
  39. int y[100001];
  40.  
  41. //1e5 * 30 * 30
  42.  
  43. const int LOGMAX = 40;
  44. const double EPS = 1e-7;
  45.  
  46. bool f(double r, double p)
  47. {
  48.     ld ret = 0;
  49.     for (int i = 1; i <= n; i++)
  50.     {
  51.         ld dx = p-x[i];
  52.         ld dy = r-y[i];
  53.         ret = max(ret, dx*dx + dy*dy);
  54.     }
  55.     return ret < (ld)r*r; //farthest squared distance
  56. }
  57.  
  58. int mx = 0;
  59. double ans = 1e18;
  60. bool ok = false;
  61.  
  62. int hits = 0;
  63.  
  64. double calc(double p) //minimum radius needed to work loc p
  65. {
  66.     double lo = 0;
  67.     double hi = (double)mx * mx;
  68.     for (int i = 1; i <= LOGMAX; i++)
  69.     {
  70.         double mid = (lo+hi)/2;
  71.         if (f(mid, p)) {hi = mid; ans = min(ans, mid); }
  72.         else lo = mid;
  73.     }
  74.     return lo;
  75. }
  76.  
  77. int main()
  78. {
  79.     //ifstream inf("");
  80.     //ofstream outf("");
  81.     cout << setprecision(15);
  82.     ios::sync_with_stdio(0); cin.tie(0);
  83.    
  84.     cin >> n;
  85.     for (int i = 1; i <= n; i++)
  86.     {
  87.         cin >> x[i] >> y[i];
  88.         if (y[i] < 0) hits++;
  89.         mx = max(mx, y[i]);
  90.         mx = max(mx, x[i]);
  91.     }
  92.     if (hits > 0) for (int i = 1; i <= n; i++) {x[i] *= -1; y[i] *= -1;}
  93.     if (hits != n && hits != 0) {cout << -1 << '\n'; return 0;}
  94.    
  95.     double lo = -2*mx;
  96.     double hi = 2*mx;
  97.     for (int i = 1; i <= LOGMAX; i++)
  98.     {
  99.         double lm = lo + (hi - lo)/3;
  100.         double rm = hi - (hi - lo)/3;
  101.         if (calc(lm) < calc(rm)) hi = rm;
  102.         else lo = lm;
  103.     }
  104.    
  105.     cout << calc(lo) << '\n';
  106.    
  107.     return 0;
  108.    
  109. }
Advertisement
RAW Paste Data Copied
Advertisement