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