Advertisement
skimono

Untitled

Apr 29th, 2022
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.23 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-9;
  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. Point base{ inf,inf };
  85.  
  86. bool cmp(Point a, Point b) {
  87.     ll ans = (a.x - base.x) * (b.y - base.y) - (b.x - base.x) * (a.y - base.y);
  88.     if (ans == 0) {
  89.         return getl(base, a) < getl(base, b);
  90.     }
  91.     else {
  92.         return ans > 0;
  93.     }
  94. }
  95.  
  96. signed main() {
  97. #ifdef _DEBUG
  98.     freopen("in.txt", "r", stdin);
  99.     freopen("out.txt", "w", stdout);
  100. #endif
  101.     freopen("hull.in", "r", stdin);
  102.     freopen("hull.out", "w", stdout);
  103.     ios_base::sync_with_stdio(0);
  104.     cin.tie(NULL);
  105.     cout.tie(NULL);
  106.     ll t = 1;
  107.     //cin >> t;
  108.     while(t--) {
  109.         ll n, i, j, x0, y0, x1, y1;
  110.         ld two = 2.0;
  111.         cin >> n;
  112.         vector <Point> a(n);
  113.         for (i = 0; i < n; i++) {
  114.             cin >> a[i].x >> a[i].y;
  115.             if (a[i].x < base.x) {
  116.                 base = a[i];
  117.             }
  118.             else if (a[i].x == base.x && a[i].y < base.y) {
  119.                 base = a[i];
  120.             }
  121.         }
  122.         sort(a.begin(), a.end(), cmp);
  123.         vector <Point> path;
  124.         path.push_back(base);
  125.         for (i = 1; i < n; i++) {
  126.             while (!path.empty()) {
  127.                 Point u = path.back();
  128.                 path.pop_back();
  129.                 if (!path.empty()) {
  130.                     x0 = a[i].x - u.x;
  131.                     y0 = a[i].y - u.y;
  132.                     x1 = path.back().x - u.x;
  133.                     y1 = path.back().y - u.y;
  134.                     ll res = x0 * y1 - x1 * y0;
  135.                     if (res > 0) {
  136.                         path.push_back(u);
  137.                         break;
  138.                     }
  139.                 }
  140.                 else {
  141.                     path.push_back(u);
  142.                     break;
  143.                 }
  144.             }
  145.             path.push_back(a[i]);  
  146.         }
  147.         ld ans = 0;
  148.         n = path.size();
  149.         cout << n << endl;
  150.         for (i = 0; i < n; i++) {
  151.             cout << (ll)path[i].x << " " << (ll)path[i].y << endl;
  152.         }
  153.         for (i = 0; i < n; i++) {
  154.             ans += (path[i].x * path[(i + 1) % n].y) - (path[(i + 1) % n].x * path[i].y);
  155.         }
  156.         cout << fixed << setprecision(1)
  157.             << fabs(ans) / two << endl;
  158.         //cout << ans << endl;
  159.     }
  160. }
  161. //痛みを受け入れる。 痛みを知っています。 痛みを感じる。 痛みを参照してください。 真の痛みを知らなければ、真の世界を理解することは不可能です。 今、あなたは痛みを知るでしょう。 神の罰!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement