[백준 2121번] 넷이 놀기 풀이

2121번: 넷이 놀기

 

N개의 좌표가 주어졌을 때, 해당 좌표들을 이용하여 만들 수 있는 가로 A, 세로 B의 직사각형을 세는 문제이다. 

 

만약, (a, b)를 직사각형의 가장 하단 왼쪽 점이라고 가정하였을 때, 가로 A, 세로 B의 직사각형을 만드는 나머지 좌표는

 

오른쪽 하단: (a+A, b)
오른쪽 상단: (a+A, b+B)

왼쪽 상단: (a, b+B)

 

이다. 따라서 N개의 좌표를 순회하면서 해당 좌표를 오른쪽 하단의 점이라 가정하고, N개의 좌표들 중 (a+A, b), (a+A, b+B), (a, b+B)가 모두 존재하는지 확인한다. 만약 존재한다면 만들 수 있는 직사각형의 수 cnt를 1 증가시킨다.

 

구현에 대한 한가지 팁은, 좌표를 저장할 때 x와 y값을 묶어 pair<int, int> 형태의 자료형으로 저장하는 것이다.  

pair<int,int> 자료형을 사용하는 경우 첫번째 int에 접근하기 위해 멤버변수 first, 두번째 int에 접근하기 위해 멤버변수 second를 사용해야 한다. 

 

또한 N가지의 좌표에서 (a+A, b), (a+A, b+B), (a, b+B)의 좌표가 있는지 확인 할 때 순차 탐색이 아닌 이분 탐색 함수(findCoord)를 사용하면 시간 복잡도를 줄일 수 있다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;
using ii = pair<int, int>;

bool findCoord(const vector<ii>& v, ii p) {

    int first = 0;
    int last = v.size()-1;
    int mid;

    while (first <= last) {
        mid = (first+last)/2;
        if (v[mid] == p)
            return true;
        else if (v[mid] > p)
            last = mid-1;
        else first = mid+1;
    }
    return false;
}

int main() {

    int N, w, h;
    scanf("%d %d %d", &N, &w, &h);
    
    vector<ii> v(N);
    for (int i=0; i<N; i++)
        scanf("%d %d", &(v[i].first), &(v[i].second));
    
    sort(v.begin(), v.end());

    int cnt = 0;
    for (int i=0; i<N; i++) {

        int x = v[i].first;
        int y = v[i].second;
        
        ii p1 = {x+w, y};
        ii p2 = {x, y+h};
        ii p3 = {x+w, y+h};

        if (findCoord(v, p1) && findCoord(v, p2) && findCoord(v, p3))
            cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}