2103 직교다각형 복원

음 하나의 직교사각형을 만드는 줄 알았는데 아니었구나. 

 

 

알고보니 각 꼭짓점이 주어졌다. 이제 길이를 어떻게 구하냐.... 한 삼일 계속 고민하다가 밥 먹다가 갑자기 떠올랐다.

한 위치를 기준으로 점을 정렬한 다음 길이를 구하면 되겠구나 

 

 

예를 들어 사각형이 저렇게 있다고 하면 (중복이 없다고 생각하자 귀찮,,) 특정 y를 기준으로 x를 정렬한 다음에 x의 길이를 구하면 되겠다 싶었다. 

 

그런데 이렇게 겹치는 경우가 생기면 어떡하지?? 싶었는데 겹치는 도형을 보면 저 중간 점 (노랑과 빨강이 겹치는 점)은 꼭짓점이 아니여서 입력으로 들어오지 않을 것이다. 악악 어려워 아무튼 해결함

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <typeinfo>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    vector<int> vx[10005];
    vector<int> vy[10005];
    
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        int inx, iny;
        
        scanf("%d %d", &inx, &iny);
        vx[inx].push_back(iny);
        vy[iny].push_back(inx);
    }
    
    int ans = 0;
    for (int i = 0; i <= 10000; i++) {
        sort(all(vx[i]));
        sort(all(vy[i]));
        
        for (int j = 0; j < vx[i].size(); j += 2) {
            ans += vx[i][j + 1] - vx[i][j];
        }
        for (int j = 0; j < vy[i].size(); j += 2) {
            ans += vy[i][j + 1] - vy[i][j];
        }
    }

    printf("%d\n", ans);
    return 0;
}