Advertisement
skimono

Untitled

May 26th, 2023
989
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.94 KB | None | 0 0
  1. /*
  2. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  3. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  4. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  5. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  6. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⢛⣉⣥⣤⣶⣶⣶⣶⣶⣶⣤⣬⣉⡛⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  7. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⣩⣴⣾⣿⣿⣿⣿⣿⣿⡿⠟⠛⠛⠻⢿⣿⣿⣷⣦⣍⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  8. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⣡⣾⣿⣿⣿⣿⣿⣿⣿⡿⢃⣴⣾⣿⠋⣁⣀⠙⣿⣿⣿⣿⣷⣌⠹⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  9. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢡⣾⣿⣿⣿⣿⣿⣿⣿⣿⡿⠇⣼⣿⣿⣿⣷⠸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  10. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣰⣿⣿⣿⣿⣿⣿⣿⡿⡋⢑⣤⣤⡙⢿⣿⡿⠟⣠⣈⠝⠻⣿⣿⣿⣿⣿⣿⣿⣆⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿
  11. ⣿⣿⣿⣿⣿⣿⣿⣿⡟⢰⣿⣿⣿⣿⣿⣿⡿⡃⣠⣾⣿⣿⣿⣷⣶⣶⣶⣾⣿⣿⣷⣄⢈⢿⣿⣿⣿⣿⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣿⣿
  12. ⣿⣿⣿⣿⣿⣿⣿⣿⠃⣿⣿⣿⣿⣿⣿⡟⠀⣴⣿⣿⣿⣿⡿⠟⠛⠛⠻⢿⣿⣿⣿⣿⣧⠉⢻⣿⣿⣿⣿⣿⣿⡈⣿⣿⣿⣿⣿⣿⣿⣿
  13. ⣿⣿⣿⣿⣿⣿⣿⡿⢸⣿⣿⣿⣿⣿⣿⢣⢰⣿⣿⣿⣿⠏⣠⣾⣿⣿⣷⣦⠹⣿⣿⣿⣿⡇⡌⣿⣿⣿⣿⣿⣿⡇⢻⣿⣿⣿⣿⣿⣿⣿
  14. ⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⣿⣿⢿⣿⣿⠸⢸⣿⣿⣿⣿⠀⣿⣿⣿⣿⣿⣿⠄⣿⣿⣿⣿⡇⠀⣿⣿⣿⣿⣿⣿⡇⢸⣿⣿⣿⣿⣿⣿⣿
  15. ⣿⣿⣿⣿⣿⣿⣿⣿⢸⣿⣿⡇⡀⣿⠋⣤⣤⣤⡙⢿⣿⣆⠹⣿⣿⣿⣿⠟⣰⣿⣿⠟⠛⠃⠢⣿⣿⣿⣿⣿⣿⡇⣾⣿⣿⣿⣿⣿⣿⣿
  16. ⣿⣿⣿⣿⣿⣿⣿⣿⡈⣿⣿⡇⢳⣤⣼⣿⣿⣿⣿⢘⣿⣿⣷⣦⣬⣤⣴⣾⣿⡿⢡⣾⣿⣿⣷⡌⢻⣿⣿⣿⣿⢁⣿⣿⣿⣿⣿⣿⣿⣿
  17. ⣿⣿⣿⣿⣿⣿⣿⣿⢧⠸⣿⣿⣄⠻⠿⣿⣿⠿⠋⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣿⣿⣿⣿⠘⣿⣿⣿⠏⣼⣿⣿⣿⣿⣿⣿⣿⣿
  18. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠹⣿⣿⣿⣶⣶⣶⣶⣦⣄⡉⣛⠿⠿⠿⠿⠿⠿⠛⠉⣂⣤⣉⡉⢹⠟⣰⣿⣿⠏⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿
  19. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⡘⢿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣭⣥⣤⣤⣴⣶⣿⣿⡿⠋⢀⣡⣴⣿⡿⢋⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  20. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣆⡙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  21. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣉⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⣋⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  22. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣬⣉⡛⠻⠿⠿⠿⠿⠿⠿⠟⢛⣋⣥⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  23. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣶⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  24. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  25. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  26. ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  27. */
  28.  
  29. #pragma GCC optimize("Ofast")
  30. #pragma GCC target("avx2")
  31.  
  32. #define _CRT_SECURE_NO_WARNINGS
  33.  
  34. #include <iostream>
  35. #include <vector>
  36. #include <string>
  37. #include <algorithm>
  38. #include <cmath>
  39. #include <stack>
  40. #include <iomanip>
  41. #include <fstream>
  42. #include <string>
  43. #include <set>
  44. #include <deque>
  45. #include <queue>
  46. #include <map>
  47. #include <bitset>
  48. #include <random>
  49. #include <list>
  50. #include <unordered_map>
  51. #include <unordered_set>
  52. #include <cassert>
  53.  
  54. using namespace std;
  55.  
  56. typedef long long ll;
  57. typedef unsigned long long ull;
  58. typedef long double ld;
  59. typedef string str;
  60. //typedef __int128 ultraint;
  61. #define endl "\n"
  62. #define sqrt sqrtl
  63. //#define pow fast_pow
  64.  
  65. const ll inf = (ll)1e18 + 7;
  66. ld eps = 1e-6;
  67.  
  68. struct Point {
  69.     ld x, y;
  70. };
  71.  
  72. ld getl(Point a, Point b) {
  73.     return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
  74. }
  75.  
  76. ld getS(Point a, Point b, Point c) {
  77.     ld ab = getl(a, b);
  78.     ld bc = getl(b, c);
  79.     ld ac = getl(a, c);
  80.     ld p = (ab + bc + ac) / 2.0;
  81.     return sqrt(p * (p - ab) * (p - bc) * (p - ac));
  82. }
  83.  
  84. ld getSmn(vector <Point> &path) {
  85.     ld ans = 0;
  86.     ll i, n = path.size();
  87.     for (i = 0; i < n; i++) {
  88.         ans += (path[i].x * path[(i + 1) % n].y) - (path[(i + 1) % n].x * path[i].y);
  89.     }
  90.     return fabs(ans) / 2.0;
  91. }
  92.  
  93. struct pr {
  94.     ld a, b, c;
  95. };
  96.  
  97. pr ur_pr(Point A, Point B) {
  98.     ld a, b, c;
  99.     a = B.y - A.y;
  100.     b = A.x - B.x;
  101.     c = (-1) * (a * A.x + b * A.y);
  102.     return { a,b,c };
  103. }
  104.  
  105. Point base{ inf,inf };
  106. bool cmp(Point a, Point b) {
  107.     ll ans = (a.x - base.x) * (b.y - base.y) - (b.x - base.x) * (a.y - base.y);
  108.     if (ans == 0) {
  109.         return getl(base, a) < getl(base, b);
  110.     }
  111.     else {
  112.         return ans > 0;
  113.     }
  114. }
  115.  
  116. ld check(ld m, vector <Point>& a) {
  117.     ll i, n = a.size();
  118.     vector <Point> path1, path2;
  119.     for (i = 0; i < n; i++) {
  120.         if (a[i].x <= m) {
  121.             if (i > 0 && a[i - 1].x > m) {
  122.                 pr sup = ur_pr(a[i], a[i - 1]);
  123.                 ld y = (-sup.a * m - sup.c) / sup.b;
  124.                 path1.push_back({ m,y });
  125.                 path2.push_back({ m,y });
  126.             }
  127.             path1.push_back(a[i]);
  128.         }
  129.         else {
  130.             if (i > 0 && a[i - 1].x <= m) {
  131.                 pr sup = ur_pr(a[i], a[i - 1]);
  132.                 ld y = (-sup.a * m - sup.c) / sup.b;
  133.                 path1.push_back({ m,y });
  134.                 path2.push_back({ m,y });
  135.             }
  136.             path2.push_back(a[i]);
  137.         }
  138.     }
  139.     if ((a[0].x <= m && a[n - 1].x > m) || (a[n - 1].x <= m && a[0].x > m)) {
  140.         pr sup = ur_pr(a[0], a[n - 1]);
  141.         ld y = (-sup.a * m - sup.c) / sup.b;
  142.         path1.push_back({ m,y });
  143.         path2.push_back({ m,y });
  144.     }
  145.     return getSmn(path1) - getSmn(path2);
  146. }
  147.  
  148. signed main() {
  149. #ifdef _DEBUG
  150.     freopen("in.txt", "r", stdin);
  151.     freopen("out.txt", "w", stdout);
  152. #endif
  153.     freopen("cut.in", "r", stdin);
  154.     freopen("cut.out", "w", stdout);
  155.     ios_base::sync_with_stdio(0);
  156.     cin.tie(NULL);
  157.     cout.tie(NULL);
  158.     ll t = 1;
  159.     //cin >> t
  160.     while (t--) {
  161.         ll n, i, j, tt = 100;
  162.         cin >> n;
  163.         ld l = inf, r = -inf, m, ans = inf, id;
  164.         vector <Point> a(n);
  165.         for (i = 0; i < n; i++) {
  166.             cin >> a[i].x >> a[i].y;
  167.             l = min(l, a[i].x);
  168.             r = max(r, a[i].x);
  169.         }
  170.         if (getSmn(a) > 0) {
  171.             while (tt--) {
  172.                 m = (l + r) / 2.0;
  173.                 ld res = check(m, a);
  174.                 if (fabs(res) < ans) {
  175.                     ans = fabs(res);
  176.                     id = m;
  177.                 }
  178.                 if (res<= 0) {
  179.                     l = m;
  180.                 }
  181.                 else {
  182.                     r = m;
  183.                 }
  184.             }
  185.             cout << fixed << setprecision(6)
  186.                 << id << endl;
  187.         }
  188.         else {
  189.             cout << fixed << setprecision(6)
  190.                 << (l + r) / 2.0 << endl;
  191.         }
  192.     }
  193. }
  194. //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
  195.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement