[BOJ 17611] 직각다각형

https://www.acmicpc.net/problem/17611

17611번: 직각다각형

 

- 문제 요약

 

첫 번째 줄에 단순직각다각형의 꼭짓점 개수인 N이 주어진다. ( 4 <= N <= 100,000 )

두 번째 줄부터 N+1번째 줄까지 꼭지점의 좌표 (xi, yi)이 주어진다.

단순직각다각형과 가장 많이 교차하는 수평선 H와 수직선 V의 위치를 찾아 그때의 교차 횟수를 구하고자 한다. 단, 수평선 H는 다각형의 어떤 수평선분과도 겹쳐 놓여서는 안 되고, 유사하게 수직선 V는 다각형의 어떤 수직선분과도 겹쳐 놓여서는 안 된다.

수평선 H의 위치를 잘 정해서 주어진 단순직각다각형의 수직선분과 가장 많이 교차하는 지점을 찾을 때, 그때의 교차 횟수를 h라 하고, 유사하게 수직선 V와 주어진 단순직각다각형의 수평선분과 가장 많이 교차하는 횟수를 v라 할 때, max(h, v)를 출력하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

가로 선분이 H와 몇 번 겹치는지, 세로 선분이 H와 몇 번 겹치는지를 구한 후, 두 값 중 최댓값을 출력해주면 됩니다.

선분이 시작되는 지점에 1을 더해주고 끝나는 지점에 1을 빼주면 위 값들을 구할 수 있습니다.

 

 

- 코드 작성

 

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

#define MAX 100001
int n,result;
pair<int,int>v[MAX];
vector<pair<int,int> >arr[2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>v[i].first>>v[i].second;
	}
	for(int i=1;i<=n;i++){
		int l,r,q=i,z=i-1;
		if(q==n){
			q=n-1;
			z=0;
		}
		if(v[q].first==v[z].first){
			l=min(v[q].second,v[z].second);
            r=max(v[q].second,v[z].second);
		}
		else{
			l=min(v[q].first,v[z].first);
            r=max(v[q].first,v[z].first);
		}
		arr[i%2].push_back({l,1});
		arr[i%2].push_back({r,-1});
	}
	for(int i=0;i<2;i++){
		sort(arr[i].begin(),arr[i].end());
		int tmp=0;
		for(auto [t,v]:arr[i]){
			tmp+=v;
			result=max(result,tmp);
		}
	}
	cout<<result;
}

코드 제출 결과