ivnikkk

Untitled

May 25th, 2022 (edited)
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.48 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef pair<int, int> pii;
  9. typedef long double ld;
  10. #define Vec Point
  11. const ld EPS = 1e-13;
  12. const ld Pi = 3.14159265358979323846;
  13. int sign(ld x) {
  14.     if (x > EPS) return 1;
  15.     if (x < -EPS) return -1;
  16.     return 0;
  17. }
  18.  
  19. ld sq(ld x) {
  20.     return x * x;
  21. }
  22.  
  23. struct Point {
  24.     ld x, y;
  25.     Point() : x(0), y(0) {}
  26.     Point(ld _x, ld _y) : x(_x), y(_y) {}
  27.     Point operator-(const Point& other) const {
  28.         return Point(x - other.x, y - other.y);
  29.     }
  30.     Point operator+(const Point& other) const {
  31.         return Point(x + other.x, y + other.y);
  32.     }
  33.     Point operator*(const ld& other) const {
  34.         return Point(x * other, y * other);
  35.     }
  36.     ld operator^(const Point& other) const {
  37.         return x * other.y - y * other.x;
  38.     }
  39.     ld operator*(const Point& other) const {
  40.         return x * other.x + y * other.y;
  41.     }
  42.     ld len2() const {
  43.         return sq(x) + sq(y);
  44.     }
  45.     ld len() const {
  46.         return sqrtl(len2());
  47.     }
  48.     Point norm() const {
  49.         ld d = len();
  50.         return Point(x / d, y / d);
  51.     }
  52.     bool operator<(const Point& other) const {
  53.         if (sign(x - other.x) != 0) {
  54.             return x < other.x;
  55.         }
  56.         else if (sign(y - other.y) != 0) {
  57.             return y < other.y;
  58.         }
  59.         return false;
  60.     }
  61.     bool operator==(const Point& other) const {
  62.         return sign(x - other.x) == 0 && sign(y - other.y) == 0;
  63.     }
  64.     Point ort() {
  65.         return Point(-y, x);
  66.     }
  67.     void deb() const {
  68.         std::cerr << "(" << x << ", " << y << ")" << std::endl;
  69.     }
  70. };
  71. ostream& operator << (ostream& out, const Point& val) {
  72.     return out << val.x << ' ' << val.y;
  73. }
  74. istream& operator >> (istream& in, Point& val) {
  75.     return in >> val.x >> val.y;
  76. }
  77. struct Line {
  78.     ld a, b, c;
  79.     Line() : a(0), b(0), c(0) {}
  80.     Line(const Point& x, const Point& y) : a(y.y - x.y), b(x.x - y.x), c(x.y* y.x - y.y * x.x) {
  81.         ld d = Point(a, b).len();
  82.         a /= d, b /= d, c /= d;
  83.         if (sign(a) == -1) {
  84.             a = -a;
  85.             b = -b;
  86.             c = -c;
  87.         }
  88.         else if (sign(a) == 0 && sign(b) == 0) {
  89.             a = 0;
  90.             b = -b;
  91.             c = -b;
  92.         }
  93.     }
  94.     bool operator==(const Line& other) const {
  95.         return sign(a - other.a) == 0 && sign(b - other.b) == 0 && sign(c - other.c) == 0;
  96.     }
  97. };
  98. ld get_S(vector<Point>& p) {
  99.     int n = (int)p.size();
  100.     ld ans = 0.0000000;
  101.     for (int i = 0; i < n; i++) {
  102.         ans += (p[i] ^ p[i + 1 < n ? i + 1 : 0]);
  103.     }
  104.     return fabs(ans) / 2.0000;
  105. }
  106. bool line_cross(const Line& a, const Line& b, Point& ans) {
  107.     ld d = (a.b * b.a - a.a * b.b);
  108.     if (sign(d) == 0)
  109.         return false;
  110.     ans.x = (b.b * a.c - b.c * a.b) / d;
  111.     ans.y = (b.c * a.a - a.c * b.a) / d;
  112.     return true;
  113. }
  114. bool is_point_on_seg(const Point& a, const Point& b, const Point& x) {
  115.     return sign((a - b).len() - (a - x).len() - (b - x).len()) == 0;
  116. }
  117. void revector(vector<Point>& sub) {
  118.     for (int i = 1; i < (int)sub.size();i++) {
  119.         sub[i] = sub[i] - sub[0];
  120.     }
  121. }
  122. void addvector(vector<Point>& sub) {
  123.     for (int i = 1; i < (int)sub.size(); i++) {
  124.         sub[i] = sub[i] + sub[0];
  125.     }
  126. }
  127. bool check(vector<Point>& p, ld& mid) {
  128.     auto cmp = [&](const Point& a, const Point& b) {
  129.         if (sign(a ^ b)) {
  130.             return sign(a ^ b) == 1;
  131.         }
  132.         else {
  133.             return sign(b.len2() - a.len2()) == 1;
  134.         }
  135.     };
  136.     Line ins(Point(mid, 0), Point(mid, 1));
  137.     vector<Point> left, right;
  138.     for (int i = 0; i < (int)p.size(); i++) {
  139.         if (sign(p[i].x - mid) == 1) {
  140.             right.push_back(p[i]);
  141.         }
  142.         else {
  143.             left.push_back(p[i]);
  144.         }
  145.         Point ans;
  146.         if (line_cross(Line(p[i], p[i + 1 < (int)p.size() ? i + 1 : 0]), ins, ans)) {
  147.             if (is_point_on_seg(p[i], p[i + 1 < (int)p.size() ? i + 1 : 0], ans)) {
  148.                 left.push_back(ans);
  149.                 right.push_back(ans);
  150.             }
  151.         }
  152.     }
  153.     revector(left), revector(right);
  154.     if(!left.empty())stable_sort(left.begin() + 1, left.end(), cmp);
  155.     if(!right.empty())stable_sort(right.begin() + 1, right.end(), cmp);
  156.     addvector(left), addvector(right);
  157.     return sign((get_S(left) - get_S(right))) == 1;
  158. }
  159. signed main() {
  160. #ifdef _DEBUG
  161.     freopen("input.txt", "r", stdin);
  162.     freopen("output.txt", "w", stdout);
  163. #endif
  164.     ios_base::sync_with_stdio(false);
  165.     cin.tie(nullptr);
  166.     cout.tie(nullptr);
  167.     freopen("cut.in", "r", stdin);
  168.     freopen("cut.out", "w", stdout);
  169.     cout << fixed << setprecision(6);
  170.     int n;
  171.     cin >> n;
  172.     vector<Point> p(n);
  173.     for (int i = 0; i < n; i++) {
  174.         cin >> p[i];
  175.     }
  176.     ld l = -1e3 - 1, r = 1e3 + 1;
  177.     for (int lg = 0; lg < 200; lg++) {
  178.         ld m = (l + r) / 2.0;
  179.         if (check(p, m)) {
  180.             r = m;
  181.         }
  182.         else {
  183.             l = m;
  184.         }
  185.     }
  186.     cout << r;
  187. }
Add Comment
Please, Sign In to add comment