백준 2171번: 직사각형의 개수 (C++)

https://www.acmicpc.net/problem/2171

2171번: 직사각형의 개수

---

Solved By: set

 

Brute-Force로 4중 for문으로 만들어서 시간 초과로 헤매고 있을 때, 이 풀이를 발견했는데 정말 충격입니다.

(https://jason9319.tistory.com/385)

점들의 입력을 받으면서 set에서도 좌표의 입력을 받아냅니다.

그리고, 2중 for문 Brute-Force로 두 가지 점을 고릅니다. 이 두 가지 점은 서로 대각선 상에 위치해야 합니다. 즉, x좌표 y좌표 모두 달라야 한다는 뜻입니다.

고른 두 점을 a, b라고 했을 때, set을 통해 a.x와 b.y를 가지는 좌표, a.y와 b.x를 가지는 좌표가 있는지 확인합니다. 정말 충격적입니다..

 

예외로 고른 두 점이 직사각형의 우상점, 좌하점일 때, Brute-Force를 통해 우좌점, 좌상점이 잡혀서 같은 직사각형을 만들 수 있으므로 /= 2를 해주어야 합니다.

 

이상하게 set은 구조체 형태로 사용하면 에러가 나더군요.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct Point{
    int x, y;
};

vector<Point> v;
set<pair<int, int>> st;
int n;
int res = 0;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++){
        int a, b; cin >> a >> b;
        v.push_back({a, b});
        st.insert({a, b});
    }
    
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(v[i].x != v[j].x && v[i].y != v[j].y){
                if(st.count({v[i].x, v[j].y}) && st.count({v[j].x, v[i].y})){
                    res++;
                }
            }
        }
    }
    
    cout << res / 2;
    
    return 0;
}