Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <set>
- #define task "HLCOVER"
- using namespace std;
- using ll = long long;
- using ld = long double;
- template<class T>
- void read(T &x){
- register int c;
- x = 0;
- bool neg = 0;
- while((c = getchar()) && c < '0' || c > '9');
- for(; c >= '0' && c <= '9'; c = getchar())
- x = x * 10 + c - '0';
- }
- const int N = 5e3 + 2;
- int n;
- struct Point{
- ll x, y;
- Point() {}
- Point(ll u, ll v){
- x = u;
- y = v;
- }
- bool operator < (const Point &a) const{
- return x < a.x
- || (x == a.x && y < a.y);
- }
- };
- using TPoint = Point*;
- Point a[N], b[N];
- TPoint s[N];
- void Read(){
- //cin >> n;
- read(n);
- for(int i = 1; i <= n; ++i){
- //cin >> a[i].x >> a[i].y;
- read(a[i].x);
- read(a[i].y);
- //a[i].x = abs(a[i].x);
- //a[i].y = abs(a[i].y);
- s[i] = &a[i];
- }
- sort(s + 1, s + n + 1, [&](TPoint &a, TPoint &b){return *a < *b;});
- for(int i = 1; i <= n; ++i)
- b[i] = *s[i];
- }
- bool Check(int i, int j){
- if(b[i].x <= b[j].x && b[i].y <= b[j].y)
- return true;
- ll S1 = b[i].x * b[j].y,
- S2 = (b[j].x - b[i].x) * (b[i].y - b[j].y);
- return S1 >= S2;
- }
- struct com{
- bool operator () (const TPoint &x, const TPoint &y) const{
- return *x < *y;
- }
- };
- void Solve(){
- for(int i = 1; i <= n; ++i)
- for(int j = i + 1; j <= n; ++j)
- if(b[i].x <= b[j].x && b[i].y <= b[j].y)
- b[i] = b[j] = Point(max(b[i].x, b[j].x),
- max(b[i].y, b[j].y));
- for(int i = 1; i <= n; ++i)
- for(int j = i + 1; j <= n; ++j)
- if(Check(i, j))
- b[i] = b[j] = Point(max(b[i].x, b[j].x),
- max(b[i].y, b[j].y));
- set<TPoint, com> s;
- ll ans = 0;
- for(int i = 1; i <= n; ++i)
- if(s.find(&b[i]) == s.end()){
- //cout << b[i].x << " " << b[i].y << "\n";
- ans += b[i].x * b[i].y * 4;
- s.insert(&b[i]);
- }
- cout << ans;
- }
- int32_t main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0); if(fopen(task".INP", "r"))
- freopen(task".INP", "r", stdin),
- freopen(task".OUT", "w", stdout);
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment