백준 5419 (C++) 북서풍

최초 업로드: 2025-04-20 14:48:09

최근 수정 시간: 2025-07-25 09:29:23

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] 북서풍

#### [문제 링크](https://www.acmicpc.net/problem/5419)

## 문제 설명

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.

작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 xi, yi가 주어진다. 두 섬의 좌표가 같은 경우는 없다. (-109 ≤ xi, yi ≤ 109)

## 출력

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

## 풀이
#### 임의의 한 점을 기준으로 왼쪽 위에 있는 점의 합을 구하는 문제입니다. y의 범위가 너무 넓어서 최대 0~75000으로 압축을 해주었습니다. 그리고 x가 작은 순, y가 큰 순을 기준으로 정렬하여, 세그먼트 트리를 이용하여 각 정점마다 x가 작고, y가 큰 정점의 수를 구해주었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;
const int MAX = 75000*3;
int _size=1, arr[MAX];

bool comp1(P a, P b) {
 return a.second>b.second || a.second==b.second && a.first<b.first;
}

bool comp2(P a, P b) {
 return a.first<b.first || a.first==b.first && a.second>b.second;
}

void update(int y) {
    int nodeNum = _size/2+y;
    arr[nodeNum]++;
    while(nodeNum>1) {
        nodeNum>>=1;
        arr[nodeNum] = arr[nodeNum*2]+arr[nodeNum*2+1];
    }
}

int getCnt(int L, int R, int nodeNum, int nodeL, int nodeR) {
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return arr[nodeNum];
 int mid = (nodeL+nodeR)/2;
 return getCnt(L, R, nodeNum*2, nodeL, mid) + getCnt(L, R, nodeNum*2+1, mid+1, nodeR);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 while(_size<75000) _size<<=1;
 _size<<=1;

int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        memset(arr, 0, sizeof arr);

vector v(n);
 for(int i=0;i<n;i++) cin >> v[i].first >> v[i].second;

// y좌표 재설정
 sort(v.begin(), v.end(), comp1);
 int cnt=75000;
 for(int i=0;i<n;i++) {
 v[i].second = --cnt;
 }

// x좌표가 작은 순, y좌표가 높은 순으로 순서대로 넣기
 long long total=0;
 sort(v.begin(), v.end(), comp2);
 for(auto p:v) {
 total += getCnt(p.second, 75000, 1, 0, _size/2-1);
 update(p.second);
 }
 cout << total << '\n';
 }
}
```