시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 8 4 4 57.143%

문제

계산기하 분야에서 삼각분할은, 다음과 같은 조건을 만족하는 삼각형의 집합을 뜻한다.

  • 삼각형의 각 꼭지점은 다각형에 있는 꼭지점 중 하나이다.
  • 삼각형끼리는 겹쳐서 안되며, 삼각형들의 합집합은 다각형과 동일하다.

볼록 다각형이라 함은. 다각형 내부의 내각이 모두 180도 미만인, 변이 3개 이상인 도형을 뜻한다.

볼록 다각형이 주어졌을 때, 우리는 이 볼록 다각형을 두개의 볼록 다각형으로 분할하는 직선을 다각형의 절단선이라고 정의한다.

삼각분할된 볼록다각형이 주어지며, 각각의 삼각분할된 삼각형들은 내부가 주어진 색상 Ci로 칠해져 있다. 다각형 내부의 임의의 색상이 같은 점 쌍이, 다른 조각으로 분할되는 일이 없도록 최대한 많은 절단선을 그었을 때, 몇개의 절단선을 그을 수 있는가?

입력

첫번째 줄에 다각형의 정점 수 n이 주어진다. (3 <= n <= 100,000)

이후 n-2개의 줄에 분할된 삼각형의 정보가 네 정수 a b c d 형태로 주어진다. 이는 주어진 삼각형이 다각형의 정점 a, b, c를 세 꼭지점으로 하며, 내부가 d라는 색상으로 칠해져 있음을 뜻한다. (1 <= a, b, c, d <= n)

입력으로 주어진 다각형은 문제에서 주어진 조건을 만족한다.

출력

다각형을 분할하는 최대의 절단선의 개수를 출력한다.

예제 입력

5
1 2 3 2
4 5 1 1
3 1 4 2

예제 출력

1

예제 입력 2

6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

예제 출력 2

0

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 5번

  • 문제를 번역한 사람: koosaga