[백준, BOJ 14865] 곡선 자르기 (java)

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

14865번: 곡선 자르기

---

문제

컴퓨터 그래픽 캔버스는 컴퓨터 화면에서 그림을 그릴 수 있는 직사각형 영역을 말한다. 캔버스는 2차원 좌표 평면처럼 각 점의 위치를 좌표로 표시한다. 캔버스의 정중앙 점이 원점 (0,0)이고, 오른쪽으로 갈수록 x좌표 값이 커지고, 위쪽으로 갈수록 y좌표 값이 커진다.

창수는 마우스를 이용하여 캔버스에 그림을 그리고 있다. 지금은 캔버스에 곡선을 그리는데, 시작점과 끝점이 붙어있는 것 외에는 중간에 선이 교차하거나 붙는 경우가 없다. 곡선을 다 그린 다음, 캔버스에서 x축의 아래쪽 영역을 깨끗이 지우면 아래 그림처럼 경계선이 서로 만나지 않는 봉우리들의 패턴이 나타난다. 여기서 봉우리는 시작점과 끝점이 x축 상에 있는 곡선 부분과 x축으로 둘러싸인 영역을 말한다. 아래 그림의 예에서는 5개의 봉우리가 나타난다.

마우스로 그린 곡선은 컴퓨터에 의해 수직 선분과 수평 선분들로 구성된 경로의 형태로 메모리에 저장된다. 따라서 창수가 그린 곡선의 경우는 수평 선분과 수직 선분이 한 번씩 번갈아가며 이어진 경계선을 가진 직교다각형의 형태로 저장된다. 이 직교다각형의 모든 꼭짓점은 서로 다르며, 연속한 두 변 이외에는 어떤 두 변도 만나지 않는다. 직교 다각형의 형태로 변환된 예를 아래 그림에서 볼 수 있다.

창수는 이 직교다각형을 입력으로 받아 x축의 위쪽 영역에 나타나는 봉우리들 중에서, 다른 봉우리에 의해 포함되지 않는 봉우리 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 구하는 프로그램을 작성하려고 한다. 위 그림에서는 다른 봉우리에 의해 포함되지 않는 봉우리 개수는 3이고 다른 봉우리를 포함하지 않는 봉우리 개수는 4이다.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 곡선을 표현하는 직교다각형의 꼭짓점의 개수 N(4 ≤ N ≤ $10^6$)이 주어진다. 다음 N개의 각 줄에는 직교다각형의 경계선을 따라갈 때 만나는 꼭짓점 순서대로 각 꼭짓점의 좌표가 주어진다. 이 순서의 방향은 가장 왼쪽에 있는 수직 선분인 변을 볼 때 아래에서 위로 올라가는 방향이다. 각 좌표는 x좌표와 y좌표가 공백을 사이에 두고 주어지며, x좌표와 y좌표 모두 $-10^9$ 보다 크거나 같고 $10^9$보다 작거나 같다. 또한 y좌표가 0인 경우는 없으며 x축과 교차하는 변이 반드시 하나 이상 존재한다.

출력

표준 출력으로, 입력으로 주어진 직교다각형에 의해서 나타나는 봉우리 패턴에서 다른 봉우리에 의해 포함되지 않는 봉우리 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 공백을 사이에 두고 출력한다.

서브태스크

번호	배점	제한
1	11	N ≤ 1,000이고 입력으로 주어지는 꼭짓점의 x좌표와 y좌표는 -1,000보다 크거나 같고 1,000보다 작거나 같다.
2	24	N ≤ 10,000
3	65	원래의 제약조건 이외에 아무 제약조건이 없다.

728x90

 

예제 입력 1

14
-4 -4
-4 3
3 3
3 -2
1 -2
1 1
-1 1
-1 -1
-2 -1
-2 2
-3 2
-3 -2
0 -2
0 -4

예제 출력 1

1 2

 

예제 입력 2

4
1 1
1 -1
-1 -1
-1 1

예제 출력 2

1 1

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static ArrayList<int[]> list;
	static int count1; // 다른 봉우리에 의해 포함되지 않는 봉우리 개수
	static int count2; // 다른 봉우리를 포함하지 않는 봉우리 개수
	
	private static int count(int idx) {
		boolean isCount2 = true;
		int j;
		for (j = idx + 1; j < list.size();) { // 한 봉우리 사이에 다른 봉우리가 있는지 확인
			if(list.get(idx)[1] > list.get(j)[0]) { // 다음 봉우리가 idx 봉우리 사이에 있다면
				count1--; // j 봉우리가 idx 봉우리에 포함되므로 count1 - 1
				isCount2 = false; // idx 봉우리가 다른 봉우리를 포함하므로 count2를 + 1하지 않기 위해 false로 바꿈
				j = count(j); // 포함된 봉우리에 대해 재귀
			}
			else break;
		}
		if(isCount2) count2++; // 포함된 봉우리가 없었다면 count2 + 1
		
		return j;
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 꼭짓점의 개수 N 입력
		int N = Integer.parseInt(br.readLine());
		
		// 봉우리의 정보를 담을 스택(밑에서 위로 올라오는 점이면 push, 위에서 밑으로 내려가는 점이면 pop)
		Stack<Integer> stack = new Stack<>();
		// 봉우리의 왼쪽 끝점을 담을 리스트
		list = new ArrayList<>();
		
		// 꼭짓점 정보 입력 받는다.
		int[] p1 = new int[2];
		
		st = new StringTokenizer(br.readLine());
		p1[0] = Integer.parseInt(st.nextToken());
		p1[1] = Integer.parseInt(st.nextToken());
		
		for (int i = 1; i < N; i++) {
			int[] p2 = new int[2]; // 다음 꼭짓점 정보 입력
			st = new StringTokenizer(br.readLine());
			p2[0] = Integer.parseInt(st.nextToken());
			p2[1] = Integer.parseInt(st.nextToken());
			
			if(p1[0] == p2[0]) { // 두 점의 x 값이 같을 때
				// 밑에서 위로 올라가는 방향이라면
				if((p1[1] < 0 && p2[1] > 0)){ 
					stack.push(p1[0]); // 봉우리의 시작이므로 stack에 넣어줌
				}
				// 위에서 아래로 내려오는 방향이라면
				if(p1[1] > 0 && p2[1] < 0) {
					if(stack.isEmpty()) { // 스택이 비었을때만(맨 처음에 위에서 아래로 내려오는 방향으로 봉우리가 들어왔다면)
						stack.push(p1[0]); // 스택에 넣어줌
					}
					else {
						int x = stack.pop();
						// 왼쪽 끝점을 0인덱스, 오른쪽 끝점을 1인덱스
						int x1 = x < p1[0] ? x : p1[0];
						int x2 = x > p1[0] ? x : p1[0];
						list.add(new int[] {x1, x2});
					}
				}
			}
			p1 = p2; // 다음 꼭짓점 정보를 비교하기 위해 p2 정보를 p1으로 바꿔줌.
		}
		// stack에 봉우리의 끝점이 남아있다면 첫번째 입력 받은 점과 마지막 입력 받은 점이 하나의 끝점임
		if(stack.size() == 1) {
			int x = stack.pop(); // x가 맨처음 들어온 위에서 아래로 내려가는 방향의 끝점
			int x1 = x < p1[0] ? x : p1[0]; // p1는 마지막으로 들어온 점
			int x2 = x > p1[0] ? x : p1[0];
			list.add(new int[] {x1, x2});
		}
		// stack에 끝점이 두개 남아있다면, 오른쪽 끝점이 먼저 입력된 하나의 봉우리임
		else if(stack.size() == 2) {
			int s1 = stack.pop();
			int s2 = stack.pop();
			int x1 = s1 < s2 ? s1 : s2;
			int x2 = s1 > s2 ? s1 : s2;
			list.add(new int[] {x1, x2});
		}
		
		list.sort((o1, o2) -> o1[0] - o2[0]); // 봉우리의 왼쪽 끝점을 기준으로 정렬
		
		count1 = list.size();
		count2 = 0;
		
		if(list.size() == 1) { // 봉우리가 한개라면
			count1 = 1;
			count2 = 1;
		}
		else { // 봉우리가 한개 이상이라면
			for (int i = 0; i < list.size();) {
				i = count(i);
			}
		}
		
		// 출력
		System.out.println(count1 + " " + count2);
		
	}

}