[라인 스위핑+구간트리] 북서풍

5419번: 북서풍 (acmicpc.net)

 

문제

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

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

입력

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

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

출력

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

 

---

<참고>

스위핑 기법(Sweeping Algorithm.. : 네이버블로그 (naver.com)

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)

라인 스위핑과 구간트리(펜윅, 세그먼트) 를 이용하여 푼다는 힌트를 보고 오랫동안 생각하여 푼 문제....

 

 

1. x 축 오름차순, y 축 내림차순 정렬.

2. 이 순서대로 라인 스위핑하면, 현재 섬 쿼리할 때, 지나온 모든 섬들이 x축에 대해선 북서풍 조건에 만족한다고 단정할 수 있다.

3. 남은 것은 지나온 섬들 중, 현재 섬의 y 보다 큰 것들이 몇개 있었냐 세야하는 것.

• y 값 마다 해당하는 섬의 갯수가 있을 것이고, 일정 범위의 총 갯수 ( 구간합) 를 빠르게 구하는 방법은 펜윅트리를 이용하는 것.
• y축 값은 범위가 (-10e9 ≤ xi, yi ≤ 10e9) 이므로, 펜윅트리를 위해 인덱스(정수)로 재배치를 해야해서 "좌표 압축" 이라는 것을 먼저 진행함.
  • 그렇게함으로서 y는 값의 범위가 0,1,2,..... 로 상대적 재배치 될 것임.
• 현재 섬의 y 보다 큰 범위의 구간합을 펜윅트리를 이용하여 구하고 answer에 더한 다음, 
• 곧 과거 섬이 될 현재 섬의 y로 펜윅트리의 구간을 업데이트한다.
• 가장 끝 섬까지 쿼리 진행.

 

//북서풍 구하기. (최대 75000개, 범위 -10e9 ~ 10e9)
bool SortComapare(pair<int, int>& a, pair<int, int>& b)
{
    if (a.first == b.first)
    {
        return a.second > b.second;
    }
    return a.first < b.first;
}

void UpdateFenwick(vector<int>& fenwick, int idx, int diff)
{
    while (idx < fenwick.size())
    {
        fenwick[idx] += diff;
        idx += idx & -idx;
    }
}

int GetValueFenwick(vector<int>& fenwick, int idx)
{
    int sum = 0;
    while (idx > 0)
    {
        sum += fenwick[idx];
        idx -= idx & -idx;
    }
    return sum;
}

void Main()
{
    vector<pair<int, int>> island = /*{ {-10, -10 }, { -10, 10}, {10, -10}, {10, 10} }*/{ {1, 3}, { 2, 2}, {3, 1} };
    vector<int> Y_Array(island.size(), 0);
    map<int, int> Ycoord;
    int answer = 0;

    // 백준이라면 입력과정이 있기때문에, 이 과정이 필요 없음.
    transform(island.begin(), island.end(), Y_Array.begin(), [](pair<int, int>& a)->int {
        return a.second;
        });
    sort(Y_Array.begin(), Y_Array.end());
    Y_Array.erase(unique(Y_Array.begin(), Y_Array.end()), Y_Array.end());   // y축 범위 압축 진행

    for (int i = 0; i < Y_Array.size(); ++i)
    {
        if (Ycoord.find(Y_Array[i]) == Ycoord.end())
            Ycoord[Y_Array[i]] = i;     // Original y축에 대한 압축y 변환 테이블.
    }
    ////.........

    sort(island.begin(), island.end(), SortComapare);

    vector<int> Fenwick(Ycoord.size()+1, 0);

    for (int i = 0; i < island.size(); ++i)
    {
        answer += GetValueFenwick(Fenwick, Fenwick.size() - 1) - GetValueFenwick(Fenwick, Ycoord[island[i].second]);
        UpdateFenwick(Fenwick, Ycoord[island[i].second] + 1, 1);
    }

    cout << "북서풍 경우의 수 : " << answer << endl;
}

 

 

백준방식 참고

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int islandNum = 0;
        cin >> islandNum;
        
        vector<pair<int, int>> island;
        vector<int> Y_Array;
        for(int i=0; i<islandNum; ++i)
        {
            int x,y;
            cin >> x >> y;
            island.push_back({x,y});
            Y_Array.push_back(y);
        }
        
        long long answer = 0;
    
        sort(Y_Array.begin(), Y_Array.end());
        Y_Array.erase(unique(Y_Array.begin(), Y_Array.end()), Y_Array.end());
    	
        // y축 압축을 섬 배열에 직접 적용
        for (unsigned int i = 0; i < island.size(); ++i)
        {
            int idx = lower_bound(Y_Array.begin(), Y_Array.end(), island[i].second) - Y_Array.begin();
            island[i].second = idx;
        }
    
        sort(island.begin(), island.end(), SortComapare);
    
        vector<int> Fenwick(Y_Array.size()+1, 0);
    
        for (unsigned int i = 0; i < island.size(); ++i)
        {
            answer += GetValueFenwick(Fenwick, Fenwick.size() - 1) - GetValueFenwick(Fenwick, island[i].second);
            UpdateFenwick(Fenwick, island[i].second + 1, 1);
        }
        
        cout << answer << endl;
    }
    
    return 0;
}