[ICPC] Rectilinear Regions

백준 14957번으로 풀어본 icpc 문제

 

u계단이 위에 있을 때 계단 사이의 공간 크기를 전부 구하는 문제였다

뭔가,,,이런 상황을 푸는 알고리즘이 있을 것 같은데 이론 공부가 부족해서 그냥 대충 해봐야지 하고 시작했다

생각은 되게 금방했는데 index 다루는데 실수가 많아서 오래 걸렸던 문제

바로 코딩 들어가지 말고 앞으로는 노트에 인덱스 정리하고 코딩 시작해야겠다ㅠㅠ

 

 

이런 순서로 움직이면서 rectilinear region의 개수와 넓이를 세었다

이 때 시작점과 끝점 처리하는곳에서 실수가 있었는데 시작점과 끝점은 음의 무한대, 양의 무한대로 생각하면 된다

그래서 두 계단이 교차 되고 나서야 왼쪽,오른쪽이 닫혀서 넓이로 셀 수 있다

계단의 시작점 말고 rectliner region이 만들어질 수 있는 시작점과 끝점을 두개의 while문을 이용해서 확인해주었다

그리고 linear한 region들은 하나로 세야 해서 boolean 함수를 하나 넣어줘서 연속하는지 아닌지 확인했다

 

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int l_y[25005];
int l_x[25005];
 
int u_y[25005];
int u_x[25005];
 
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
 
    for(int i = 0 ; i < n ; i++) scanf("%d %d",&l_y[i],&l_x[i]);
    scanf("%d",&l_y[n]);
    l_x[n] = 10000000; // inf
 
    for(int i = 0 ; i < m ; i++) scanf("%d %d",&u_y[i],&u_x[i]);
    scanf("%d",&u_y[m]);
    u_x[m] = 10000000; // inf
 
    int l_idx = 0,u_idx=0,cnt=0; 
 
    // 시작 위치 찾기
    int bigger; // 1 - u, 2 - l
    if(u_y[0]>l_y[0]) bigger = 1;
    else bigger = 2;
 
    while(l_idx<n&&u_idx<m){
        if(bigger == 1 && u_y[u_idx] <= l_y[l_idx]) break;
        else if(bigger == 2 && u_y[u_idx] >= l_y[l_idx]) break;
 
        // 끝나는 점의 x값이 작은 계단의 index를 증가
        if(u_x[u_idx]>l_x[l_idx]) l_idx++;
        else u_idx++;
    }
 
    int l_idx_max=n,u_idx_max=m;
 
    // 끝 위치 찾기
    if(u_y[m]>l_y[n]) bigger = 1;
    else bigger = 2;
    while(l_idx_max>0&&u_idx_max>0){
        if(bigger == 1 && u_y[u_idx_max] <= l_y[l_idx_max]) break;
        else if(bigger == 2 && u_y[u_idx_max] >=  l_y[l_idx_max]) break;
 
        // 끝나는 점의 x값이 큰 계단의 index를 감소
        if(u_x[u_idx_max-1]<l_x[l_idx_max-1]) l_idx_max--;
        else u_idx_max--;
    }
 
    long long int ans = 0;          // int로 저장하면 범위를 벗어난다
    bool closed = false;            // 연결되어 있는 직사각형은 하나로 취급
 
    while(l_idx<=l_idx_max&&u_idx<=u_idx_max){   
        if(u_y[u_idx]>l_y[l_idx]){ 
            if(!closed) {
                cnt++;
                closed = true;
            }
            
            // 끝점의 최소값 - 시작점의 최대값 == 겹치는 부분 ( 가로 )
            long long int horizontal = min(u_x[u_idx],l_x[l_idx])-max(u_x[u_idx-1],l_x[l_idx-1]);
 
            // y값의 차 ( 세로 )
            long long int vertical = u_y[u_idx]-l_y[l_idx];
            ans += vertical*horizontal;
        }
        else closed=false;
 
        // 끝나는 점의 x값이 작은 계단의 index를 증가
        if(u_x[u_idx]>=l_x[l_idx]) l_idx++;
        else u_idx++;
    }
    printf("%d %lld\n",cnt,ans);
}
 

 

백준 제출 현황 보니까 내 코드 반도 안되는 길이로 푼 사람들도 있던데 

요즘 코드가 너무 길어지는 것 같아서 짧고 깔끔하게 푸는 연습도 해봐야겠다