fork download 
  1. #include<bits/stdc++.h> //NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. const int N = 1e5 + 5;
  9. int n;
  10. pii a[N];
  11. int calcS(pii a, pii b, pii c) {
  12.     return (a.ft - b.ft) * c.sc + (b.ft - c.ft) * a.sc + (c.ft - a.ft) * b.sc;
  13. }
  14. pii S[N], T[N];
  15. int szS = 0, szT = 0;
  16.  
  17. signed main() {
  18.     if (ifstream("XAYDUNGRAO.INP")) {
  19.         freopen("XAYDUNGRAO.INP", "r", stdin);
  20.         freopen("XAYDUNGRAO.OUT", "w", stdout);
  21.     }
  22.     cin >> n;
  23.     for (int i = 1; i <= n; i++) cin >> a[i].ft >> a[i].sc;
  24.     sort(a + 1, a + n + 1, [&] (pii &x, pii &y) {
  25.         if (x.sc != y.sc) return x.sc < y.sc;
  26.         return x.ft < y.ft;
  27.     });
  28.     for (int i = 1; i <= n; i++) {
  29.         while(szS >= 2 && calcS(S[szS - 1], S[szS], a[i]) >= 0) szS--;
  30.         S[++szS] = a[i];
  31.  
  32.         while(szT >= 2 && calcS(T[szT - 1], T[szT], a[i]) <= 0) szT--;
  33.         T[++szT] = a[i];
  34.     }
  35.     for (int i = szT - 1; i > 1; i--) S[++szS] = T[i];
  36. //    for (int i = 1; i <= szS; i++) cerr << S[i].ft << " " << S[i].sc << "\n";
  37.     long long val = 0;
  38.     for (int i = 1; i < szS; i++) {
  39.         val += (S[i + 1].sc * S[i].ft - S[i + 1].ft * S[i].sc);
  40.     }
  41.     val += (S[1].sc * S[szS].ft - S[1].ft * S[szS].sc);
  42.     val = abs(val);
  43.     cout << szS << "\n";
  44.     if (val & 1) cout << val / 2 << ".5\n";
  45.     else cout << val / 2 << ".0\n";
  46.     for (int i = 1; i <= szS; i++) cout << S[i].ft << " " << S[i].sc << "\n";
  47. }
  48.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
0
0.0
https://ideone.com/XzClnH
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!