[백준]직각다각형(17611)

문제 링크 : [백준]직각다각형(17611)

17611번: 직각다각형

문제 설명

모든 선분이 x축 혹은 y축과 평행한 선분들로 이루어진 직각다각형이 주어집니다.

이때, x축과 평행한 선분을 임의의 위치에 긋거나, y축과 평행한 선분을 임의의 위치에 그어 주어진 직각다각형과 교차하는 점들을 각각 셉니다.

그때 가장 많이 교차하는 선분이 몇개의 선분과 교차하는지 구하세요.

입력

N(선분의 갯수, 4 <= N <= 100,000)

X_i Y_i(X_i, Y_i의 좌표, -500,000 <= X_i, Y_i <=500,000,점은 시계방향으로 주어집니다.)

12
0 0
0 3
1 3
1 1
2 1
2 3
5 3
5 0
4 0
4 2
3 2
3 0

 

출력

6

 

카테고리

#누적합

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. X축에 평행한 선과 Y축에 평행한 선을 나누어서 생각합니다.
2. 처음 나온 점과 두번째 점을 비교하여, X좌표가 다르다면 X축, Y좌표가 다르다면 Y축과 평행한 선분입니다.
3. 세번째 점과 네번째 점을 이은 선은 2번에서 구한 선과 평행합니다.(직각다각형이기 때문입니다.)
4. 위와 같이 첫번째점을 시작으로 i번째 점과 i+1번째 점을 이은 선분들을 처리합니다.(X축 혹은 Y축과 평행한 모든 선분)
5. 처리할 내용은 각 선분을 작은 좌표(-500,000에 가까운)를 기준으로 시작점과 끝점을 카운팅합니다.
   1. 시작점은 +1, 끝점은 -1
6. 모든 선분에 대해 카운팅을 한 후, 왼쪽에서 오른쪽으로 누적합을 구합니다.
7. 누적합은 현재 위치에 존재하는 선분의 갯수가 되고, 모든 구간에 대해 누적합이 가장 큰 수가 X축 혹은 Y축에 평행한 선분과 교차하는 선분 중 가장 많이 교차하는 점의 갯수입니다.)
8. 2번부터 7번을 반복하는데, 이번에는 두번째 점과 세번째 점을 시작으로 출발하여, N번째 점과 첫번째 점을 잇는 선분들을 가지고 선분들을 처리합니다.
9. 그러면 2번부터 생성한 선분과 정확하게 90도 차이가 나는 선분으로 2번에서 X축에 평행했다면 Y축으로 평행한 선분, Y축에 평행한 선분이었다면 X축에 평행한 선분이 됩니다.
10. 두가지를 처리한 후 둘 중 큰 수를 출력합니다.

시간복잡도

O(M)(M은 좌표 범위)

코드

#include<iostream>
#include<algorithm>
#include<string.h>
#define M 500000
#define N 1000001
using namespace std;
int n,d[N],e[100000][2],i,j,k,s,t;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(;i<n;i++)cin>>e[i][0]>>e[i][1];
    for(j=0;j<2;j++){
        memset(d,0,sizeof(d));
        for(i=j;i<n;i+=2){
            k=(i+1)%n;
            if(e[i][0]!=e[k][0]){
                d[min(e[i][0],e[k][0])+M]++;
                d[max(e[i][0],e[k][0])+M]--;
            }else{
                d[min(e[i][1],e[k][1])+M]++;
                d[max(e[i][1],e[k][1])+M]--;
            }
        }
        for(t=k=i=0;i<N;i++)k+=d[i],t=max(t,k);
        s=max(s,t);
    }
    cout<<s;
}