백준 2171 : 직사각형의 개수

문제 설명

---

2차원 좌표가 n개 주어졌을 때 이를 이용해만들 수 있는 직사각형의 개수를 구하는 문제.(이때 1 ≤ n ≤ 5,000)

---

 

n범위가 5,000으로 작기 때문에 O(n * nlongn)의 방법으로도 풀 수 있다. 주어진 모든 점으로 만들 수 있는 모든 대각선에 대해 set자료구조를 통해 나머지 두 점의 존재유무를 확인하면 되는 간단한 문제이다.

---

소스코드

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int n;
vector <pair<int, int>> vec;
set <pair<int, int>> st;

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back({x, y});
        st.insert({x, y});
    }
    int ans = 0;
    for(i=0;i<n - 1;i++) {
        for(j= i + 1;j<n;j++) {
            int x1 = vec[i].first, y1 = vec[i].second;
            int x2 = vec[j].first, y2 = vec[j].second;
            if(x1 == x2 || y1 == y2) continue;
            if(st.find({x1, y2}) != st.end() && st.find({x2, y1}) != st.end()) ans++;
        }
    }
    printf("%d", ans/2);
    return 0;
}