Advertisement
he_obviously

Untitled

Jul 7th, 2020
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC target("sse,sse2,ssse3,sse3,sse4,avx,avx2,popcnt,tune=native")
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <string>
  8. #include <queue>
  9. #include <set>
  10. #include <iomanip>
  11. #include <map>
  12. #include <algorithm>
  13. #include <cmath>
  14. #include <bitset>
  15. #include <limits.h>
  16.  
  17. using namespace std;
  18.  
  19. struct Vector {
  20.     long double x; long double y;
  21.     Vector(long double _x = 0, long double _y = 0) {
  22.         x = _x;
  23.         y = _y;
  24.     }
  25. };
  26.  
  27. Vector mn = { 1e12, 1e12 };
  28.  
  29. long double operator^(Vector a, Vector b) {
  30.     return (a.x * b.y - a.y * b.x);
  31. }
  32.  
  33. Vector operator-(Vector a, Vector b) {
  34.     return { a.x - b.x, a.y - b.y };
  35. }
  36.  
  37. bool operator==(Vector a, Vector b) {
  38.     return (a.x == b.x && a.y == b.y);
  39. }
  40.  
  41. long double len(Vector a) {
  42.     return sqrt(a.x * a.x + a.y * a.y);
  43. }
  44.  
  45. bool comp(Vector a, Vector b) {
  46.     Vector f = a - mn, s = b - mn;
  47.     if ((f ^ s) > 0) return true;
  48.     else if ((f ^ s) == 0 && len(a) > len(b)) return true;
  49.     else return false;
  50. }
  51.  
  52. istream& operator>>(istream& in, Vector& a) {
  53.     in >> a.x >> a.y;
  54.     return in;
  55. }
  56.  
  57. ostream& operator<<(ostream& out, Vector& a) {
  58.     out << a.x << " " << a.y;
  59.     return out;
  60. }
  61.  
  62. int main() {
  63.  
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0); cout.tie(0);
  66.  
  67.     int n;
  68.     cin >> n;
  69.  
  70.     vector<Vector> a(n);
  71.     map<Vector, int> m;
  72.  
  73.     for (int i = 0; i < n; ++i) {
  74.         cin >> a[i];
  75.         m[a[i]] = i + 1;
  76.         if (a[i].y < mn.y || (a[i].y == mn.y && a[i].x < mn.x)) {
  77.             mn = a[i];
  78.         }
  79.     }
  80.  
  81.     auto it = unique(a.begin(), a.end());
  82.     a.resize(distance(a.begin(), it));
  83.  
  84.     n = (int)a.size();
  85.     int index = 0;
  86.  
  87.     for (int i = 0; i < n; ++i) {
  88.         if (a[i] == mn) {
  89.             index = i;
  90.             break;
  91.         }
  92.     }
  93.  
  94.     swap(a[0], a[index]);
  95.  
  96.     sort(a.begin() + 1, a.end(), comp);
  97.  
  98.     vector<Vector> ans;
  99.  
  100.     ans.push_back(a[0]);
  101.     ans.push_back(a[1]);
  102.  
  103.     for (int i = 2; i < n; ++i) {
  104.         while (ans.size() > 1 &&
  105.             ((a[i] - ans[(int)ans.size() - 1]) ^ (ans[(int)ans.size() - 1] - ans[(int)ans.size() - 2])) >= 0) {
  106.             ans.pop_back();
  107.         }
  108.         ans.push_back(a[i]);
  109.     }
  110.  
  111.     long double p = 0, s = 0;
  112.  
  113.     ans.push_back(ans[0]);
  114.  
  115.     for (int i = 1; i < (int)ans.size(); ++i) {
  116.         p += len(ans[i] - ans[i - 1]);
  117.         s += (ans[i] ^ ans[i - 1]);
  118.     }
  119.  
  120.     cout << ans.size() - 1 << "\n";
  121.  
  122.     for (int i = 0; i < (int)ans.size() - 1; ++i) {
  123.         cout << m[a[i]] << " ";
  124.     }
  125.     cout << "\n";
  126.  
  127.     cout << fixed << setprecision(13) << p << "\n" << fabs(s / 2.0);
  128.  
  129.     return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement