직각다각형 > 문제은행



문제은행

3336 : 직각다각형

제한시간: 2Sec    메모리제한: 512mb
해결횟수: 14회    시도횟수: 41회   



 

다각형의 두 선분이 연속하는 선분의 꼭짓점을 제외하고는 만나지 않는 다각형을 단순다각형이라고 부른다.

다각형의 가 변이 x축과 y축에 평행한 다각형을 직각다각형이라고 부른다.

단순다각형이면서 직각다각형을 단순직각다각형이라 부른다.

아래 두 그림은 단순직각다각형의 예를 보여준다.

 

 

4070e241f6131e5c9ebab06998edc460_1557129

단순직각다각형이 주어질 때, 
수평선 H가 다각형의 수직선분과 몇 번 교차하는지 또는 수직선 V가 다각형의 수평선분과 몇 번 교차하는지 알고자 한다.
첫 번째 그림에서 수평선 H가 4개의 수직선분과 교차하고 수직선 V는 2개의 수평선분과 교차한다. 
두 번째 그림은 첫 번째 그림에서 수평서 H의 위치를 조금 위로 옮긴 것으로 8개의 수직선분과 교차하게 된다.

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

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

 


입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4≤n≤100,000)이 주어지고, 
이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (x1,y1)(1≤i≤n)가 차례대로 주어진다. 
주어지는 꼭지점들의 순서는 시계방향이다.
다각형의 꼭지점을 나타내는 각 좌표값은 정수이며, -500,000≤x1,y1≤500,000 이다.


표준 출력으로 각각 수평선 H, 수직선 V와 단순직각다각형의 최다 교차 횟수를 h,v라 할 때, max(h,v)를 출력한다.

채점기준
제출된 프로그램은 여러 개의 테스트 케이스로 평가되며, 맞은 테스트 케이스에 대해서 해당 테스트 케이스에 배정된 점수를 받는다. 
모든 테스트 케이스를 맞았을 시 100점을 받는다.

각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다.
  • 그룹1, 총 38점 상당의 테스트 케이스로 구성되어 있다. 각각 4≤n≤1,000을 만족한다.
  • 그룹2, 총 62점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.

  • [Copy]
    4
    -1 -1
    -1 1
    1 1
    1 -1
    [Copy]
    2


    [Copy]
    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
    [Copy]
    6






    HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
    경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
    Copyright@2010-2015 jungol. All right reserved.