Dang_Quan_10_Tin

HLCOVER - BUT STUPID

Aug 6th, 2020
927
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <set>
  5. #define task "HLCOVER"
  6. using namespace std;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. template<class T>
  11. void read(T &x){
  12.     register int c;
  13.     x = 0;
  14.     bool neg = 0;
  15.     while((c = getchar()) && c < '0' || c > '9');
  16.     for(; c >= '0' && c <= '9'; c = getchar())
  17.         x = x * 10 + c - '0';
  18. }
  19. const int N = 5e3 + 2;
  20. int n;
  21. struct Point{
  22.     ll x, y;
  23.     Point() {}
  24.     Point(ll u, ll v){
  25.         x = u;
  26.         y = v;
  27.     }
  28.     bool operator < (const Point &a) const{
  29.         return x < a.x
  30.             || (x == a.x && y < a.y);
  31.     }
  32. };
  33. using TPoint = Point*;
  34. Point a[N], b[N];
  35. TPoint s[N];
  36.  
  37. void Read(){
  38.     //cin >> n;
  39.     read(n);
  40.     for(int i = 1; i <= n; ++i){
  41.         //cin >> a[i].x >> a[i].y;
  42.         read(a[i].x);
  43.         read(a[i].y);
  44.         //a[i].x = abs(a[i].x);
  45.         //a[i].y = abs(a[i].y);
  46.         s[i] = &a[i];
  47.     }
  48.     sort(s + 1, s + n + 1, [&](TPoint &a, TPoint &b){return *a < *b;});
  49.     for(int i = 1; i <= n; ++i)
  50.         b[i] = *s[i];
  51. }
  52.  
  53. bool Check(int i, int j){
  54.     if(b[i].x <= b[j].x && b[i].y <= b[j].y)
  55.         return true;
  56.     ll S1 = b[i].x * b[j].y,
  57.        S2 = (b[j].x - b[i].x) * (b[i].y - b[j].y);
  58.     return S1 >= S2;
  59. }
  60.  
  61. struct com{
  62.     bool operator () (const TPoint &x, const TPoint &y) const{
  63.         return *x < *y;
  64.     }
  65. };
  66.  
  67. void Solve(){
  68.     for(int i = 1; i <= n; ++i)
  69.         for(int j = i + 1; j <= n; ++j)
  70.             if(b[i].x <= b[j].x && b[i].y <= b[j].y)
  71.                 b[i] = b[j] = Point(max(b[i].x, b[j].x),
  72.                                     max(b[i].y, b[j].y));
  73.     for(int i = 1; i <= n; ++i)
  74.         for(int j = i + 1; j <= n; ++j)
  75.             if(Check(i, j))
  76.                 b[i] = b[j] = Point(max(b[i].x, b[j].x),
  77.                                     max(b[i].y, b[j].y));
  78.     set<TPoint, com> s;
  79.     ll ans = 0;
  80.     for(int i = 1; i <= n; ++i)
  81.         if(s.find(&b[i]) == s.end()){
  82.             //cout << b[i].x << " " << b[i].y << "\n";
  83.             ans += b[i].x * b[i].y * 4;
  84.             s.insert(&b[i]);
  85.         }
  86.     cout << ans;
  87. }
  88.  
  89. int32_t main(){
  90.     ios::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     cout.tie(0); if(fopen(task".INP", "r"))
  93.     freopen(task".INP", "r", stdin),
  94.     freopen(task".OUT", "w", stdout);
  95.     Read();
  96.     Solve();
  97. }
  98.  
Advertisement
Add Comment
Please, Sign In to add comment