[BOJ 8889] 등고선 지도

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8889 에서 채점할 수 있습니다.

요약 )

 1) x, y 좌표의 최대값은 10억이지만, 갯수는 200만개 이하이기 때문에 좌표 압축을 통해 각각의 좌표를 1 ~ 200만으로 바꿀 수 있습니다.

 2) 최대 높이인 영역이 꼭지점을 하나 이상 포함하기 때문에, 모든 꼭지점의 높이 중 최대 높이만 구해도 전체 좌표 중 최대 높이가 됩니다.

 3) 특정 y좌표 (y1) 에 대한 segment tree를 통해, y좌표가 y1인 꼭지점(x1,y1)의 높이를 구할 수 있습니다.

segment tree 는 아래의 식이 성립하도록 설정해야 합니다.

0 ~ x1위치의 총합 = 좌표 (x1,y1) 꼭지점의 높이

이는 y = y1직선과 등고선의 교차점을 생각해 보면 설계할 수 있습니다.

등고선과 만남이 시작되는 위치에 +1, 만남이 끝나는 위치에 -1을 하는 식입니다.

 4) 각각의 y좌표에 대한 segment tree를 모두 저장할 필요없이, y=0일 때의 segment tree를 구한 다음, y=0 -> 200만으로 진행시켜 나가면서 트리가 갱신되는 부분만 고치면 됩니다. 갱신되는 부분이 어디인지는, 등고선 정보를 통해 알 수 있습니다.

위의 과정을 통하면 M = N*K <= 200만 이라고 할 때, O(M log M)이 가능합니다.

입력 & 좌표 압축 )

// code by RiKang, weeklyps.com
 
#include <bits/stdc++.h>
using namespace::std;
 
int n;
int a[20001];
int xy[20001][105][2];
int v[2000001];
int vm;
 
void input(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        for(int j=0;j<a[i];j++)
            scanf("%d %d",&xy[i][j][0],&xy[i][j][1]);
    }
    vm=0;
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        v[vm++]=xy[i][j][0];
    sort(v,v+vm);
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        xy[i][j][0] = lower_bound(v,v+vm,xy[i][j][0])-v;
    
    vm=0;
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        v[vm++]=xy[i][j][1];
    sort(v,v+vm);
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        xy[i][j][1] = lower_bound(v,v+vm,xy[i][j][1])-v;
}

 위와 같이 x좌표들을 v 배열에 모아서 정렬한 다음, 이분 검색을 통해 좌표를 압축합니다. 제일 작은 x좌표는 0, 그다음 작은 x좌표는 1, ..., 제일 큰 x좌표 = vm 으로 바뀝니다. vm <= N*K = 20000*100 이므로 200만이하로 압축되었습니다.

쿼리 정리 )

// code by RiKang, weeklyps.com
 
#include <bits/stdc++.h>
using namespace::std;
 
int n;
int a[20001];
int xy[20001][105][2];
int vm;
 
vector<pair<int,int> > q[2000001];
 
void make_query(int x1,int y1,int x2,int y2){
    if(y1==y2){
        q[y1].push_back(make_pair(x1+1,x2+1));
    }
}
 
void input(){
    for(int i=0;i<=2000000;i++) q[i].clear();
    for(int i=0;i<n;i++){
        xy[i][a[i]][0]=xy[i][0][0],xy[i][a[i]][1]=xy[i][0][1];
        for(int j=0;j<a[i];j++) make_query(xy[i][j][0],xy[i][j][1],xy[i][j+1][0],xy[i][j+1][1]);
    }
}

 각각의 y좌표에 대한 쿼리를 정리합니다.

 y1-1 에 대한 segment tree 가 존재할 때 이 것을 y1에 대한 segment tree로 바꾸려면 무엇이 필요한지를 찾아야 합니다. 이 구현에서는 y1 좌표에 있는 가로(-) 방향 간선의 정보를 저장하였습니다. 이후에 이 정보로 segment tree 를 갱신할 것입니다.

 세로 방향 간선의 경우엔 y = y1-1에서나 y = y1에서나 똑같기 때문에 업데이트할 부분이 없으므로 저장하지 않았습니다.

쿼리 처리 )

// code by RiKang, weeklyps.com
 
#include <bits/stdc++.h>
using namespace::std;
 
vector<pair<int,int> > q[2000001];
 
void process(){
    int ans=0;
    init(2000000);
    for(int i=0;i<=2000000;i++){
        for(int j=0;j<q[i].size();j++){
            update(q[i][j].first,1);
            update(q[i][j].second,-1);
        }
        for(int j=0;j<q[i].size();j++)
            ans=max(ans,query(1,q[i][j].first,1,1,tree_n));
    }
    printf("%d\n",ans);
}

 y = i 에 있는 가로(-) 방향 간선을 통해 등고선의 시작지점 & 끝지점을 업데이트 한 후, 꼭지점의 높이들을 찾아 답을 갱신합니다. 반시계 방향으로 입력이 주어지기 때문에 위와 같이 간단하게 업데이트할 수 있습니다.

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - B
// BOJ 8889 등고선 지도
 
#include <bits/stdc++.h>
using namespace::std;
 
int n;
int a[20001];
int xy[20001][105][2];
int v[2000001];
int vm;
 
vector<pair<int,int> > q[2000001];
 
// Segment tree 시작
int tree_n, tree[4294304];
void init(int n1){  // 초기화 : 아래에 깔리는 노드가 n1개
    tree_n=1;
    while(tree_n<n1){tree_n*=2;}
    for(int i=0;i<=2*tree_n;i++){tree[i]=0;}
}
void update(int po,int v1){  // po 번째값 업데이트
    po+=tree_n-1;
    tree[po]+=v1;
    while(po>1){
        po=po/2;
        tree[po]=tree[2*po]+tree[2*po+1];
    }
}
int query(int ql,int qr,int po,int l,int r){  // a~b구간, po노드가 ㅣ~r에 대응  => po=1  l=1  r=tree_n
    if(r<ql || l>qr) return 0;
    if(ql<=l && r<=qr) return tree[po];
    return query(ql,qr,2*po,l,(l+r)/2)+query(ql,qr,2*po+1,(l+r)/2+1,r);
}
// Segment tree 끝
 
void make_query(int x1,int y1,int x2,int y2){
    if(y1==y2){
        q[y1].push_back(make_pair(x1+1,x2+1));
    }
}
 
void input(){
    int n;
    for(int i=0;i<=2000000;i++) q[i].clear();
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        for(int j=0;j<a[i];j++)
            scanf("%d %d",&xy[i][j][0],&xy[i][j][1]);
    }
    vm=0;
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        v[vm++]=xy[i][j][0];
    sort(v,v+vm);
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        xy[i][j][0] = lower_bound(v,v+vm,xy[i][j][0])-v;
    
    vm=0;
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        v[vm++]=xy[i][j][1];
    sort(v,v+vm);
    for(int i=0; i<n; i++) for(int j=0; j<a[i]; j++)
        xy[i][j][1] = lower_bound(v,v+vm,xy[i][j][1])-v;
        
    for(int i=0;i<n;i++){
        xy[i][a[i]][0]=xy[i][0][0],xy[i][a[i]][1]=xy[i][0][1];
        for(int j=0;j<a[i];j++) make_query(xy[i][j][0],xy[i][j][1],xy[i][j+1][0],xy[i][j+1][1]);
    }
}
 
void process(){
    int ans=0;
    init(2000000);
    for(int i=0;i<=2000000;i++){
        for(int j=0;j<q[i].size();j++){
            update(q[i][j].first,1);
            update(q[i][j].second,-1);
        }
        for(int j=0;j<q[i].size();j++)
            ans=max(ans,query(1,q[i][j].first,1,1,tree_n));
    }
    printf("%d\n",ans);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        process();
    }
    return 0;
}