Hello_MMM

Untitled

Jun 21st, 2021
836
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <set>
  6. #include <iomanip>
  7.  
  8. using namespace std;
  9.  
  10. typedef long double ld;
  11.  
  12. const double EPS = 1E-9;
  13. const double INF = 1000000000;
  14. int steps = 60;
  15.  
  16. struct pt {
  17.     double x, y;
  18. };
  19.  
  20. istream& operator >>(istream& in, pt& p) {
  21.     in >> p.x >> p.y;
  22.     return in;
  23. }
  24.  
  25. struct line {
  26.     double a, b, c;
  27. };
  28.  
  29. double dist(double x, double y, line& l) {
  30.     return abs(x * l.a + y * l.b + l.c);
  31. }
  32.  
  33. double radius(double x, double y, vector<line>& l) {
  34.     int n = (int)l.size();
  35.     double res = INF;
  36.     for (int i = 0; i < n; ++i)
  37.         res = min(res, dist(x, y, l[i]));
  38.     return res;
  39. }
  40.  
  41. double y_radius(double x, vector<pt>& a, vector<line>& l) {
  42.     int n = a.size();
  43.     double ly = INF, ry = -INF;
  44.     for (int i = 0; i < n; ++i) {
  45.         int x1 = a[i].x, x2 = a[(i + 1) % n].x, y1 = a[i].y, y2 = a[(i + 1) % n].y;
  46.         if (x1 == x2)  continue;
  47.         if (x1 > x2)  swap(x1, x2), swap(y1, y2);
  48.         if (x1 <= x + EPS && x - EPS <= x2) {
  49.             double y = y1 + (x - x1) * (y2 - y1) / (x2 - x1);
  50.             ly = min(ly, y);
  51.             ry = max(ry, y);
  52.         }
  53.     }
  54.     for (int sy = 0; sy < steps; ++sy) {
  55.         double diff = (ry - ly) / 3;
  56.         double y1 = ly + diff, y2 = ry - diff;
  57.         double f1 = radius(x, y1, l), f2 = radius(x, y2, l);
  58.         if (f1 < f2)
  59.             ly = y1;
  60.         else
  61.             ry = y2;
  62.     }
  63.     return radius(x, ly, l);
  64. }
  65.  
  66. int main() {
  67.     int n;
  68.     cin >> n;
  69.     vector<pt> a(n);
  70.     for (pt& i : a) {
  71.         cin >> i;
  72.     }
  73.  
  74.     vector<line> l(n);
  75.     for (int i = 0; i < n; ++i) {
  76.         l[i].a = a[i].y - a[(i + 1) % n].y;
  77.         l[i].b = a[(i + 1) % n].x - a[i].x;
  78.         double sq = sqrt(l[i].a * l[i].a + l[i].b * l[i].b);
  79.         l[i].a /= sq, l[i].b /= sq;
  80.         l[i].c = -(l[i].a * a[i].x + l[i].b * a[i].y);
  81.     }
  82.  
  83.     double lx = INF, rx = -INF;
  84.     for (int i = 0; i < n; ++i) {
  85.         lx = min(lx, a[i].x);
  86.         rx = max(rx, a[i].x);
  87.     }
  88.  
  89.     for (int sx = 0; sx < steps; ++sx) {
  90.         double diff = (rx - lx) / 3;
  91.         double x1 = lx + diff, x2 = rx - diff;
  92.         double f1 = y_radius(x1, a, l), f2 = y_radius(x2, a, l);
  93.         if (f1 < f2)
  94.             lx = x1;
  95.         else
  96.             rx = x2;
  97.     }
  98.    
  99.     cout << fixed << setprecision(10) << y_radius(lx, a, l);
  100.  
  101.     return 0;
  102. }
RAW Paste Data