티스토리 뷰

알고리즘 관련/BOJ

BOJ)2171 직사각형의 개수

JASON 자손9319 2017. 12. 19. 02:50

문제: icpc.me/2171

2차원 평면위에 5000개 이하의 점이 있을 때 점들로 만들 수 있는 모든 직사각형의 수를 세는 문제이다,

n제한이 5000에 2초이므로 n^2logn 솔루션으로 풀 수 있을 것이라고 생각하였다.

n*n으로 모든 두 점에 대하여 직사각형의 대각선에 놓이는 경우를 생각하면, 나머지 대각선에 포함되는 두 점은 set을 이용해 존재여부를 log시간에 찾을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int n,res;
set<pair<int,int>> st;
vector<pair<int,int>> vt;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        vt.push_back({x,y});
        st.insert({x,y});
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(vt[i].first!=vt[j].first&&vt[i].second!=vt[j].second){
                if(st.count({vt[i].first,vt[j].second})&&st.count({vt[j].first,vt[i].second}))
                    res++;
            }
        }
    }
    printf("%d\n",res/2);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다  (0) 2018.06.24
BOJ)15673 헤븐스 키친2  (1) 2018.05.06
BOJ)2171 직사각형의 개수  (0) 2017.12.19
BOJ)14943 벼룩 시장  (0) 2017.12.18
BOJ)14950 정복자  (0) 2017.12.12
BOJ)15271 친구 팰린드롬2  (0) 2017.12.05
TAG
댓글
댓글쓰기 폼