시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 34 21 10 45.455%

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

1

예제 입력 2

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

예제 출력 2

0

힌트

W3sicHJvYmxlbV9pZCI6IjMzNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDEgXHViZDg0XHVkNTYwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjYzRcdWMwYjBcdWFlMzBcdWQ1NTggXHViZDg0XHVjNTdjXHVjNWQwXHVjMTFjIFx1YzBiY1x1YWMwMVx1YmQ4NFx1ZDU2MFx1Yzc0MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMDEgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjJkXHVjOWMwXHVjODEwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzBiY1x1YWMwMVx1ZDYxNVx1YjA3Y1x1YjlhY1x1YjI5NCBcdWFjYjlcdWNjZDBcdWMxMWMgXHVjNTQ4XHViNDE4XHViYTcwLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5XHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YWNmYyBcdWIzZDlcdWM3N2NcdWQ1NThcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1Yjc3YyBcdWQ1NjhcdWM3NDAuIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM3NTggXHViMGI0XHVhYzAxXHVjNzc0IFx1YmFhOFx1YjQ1MCAxODBcdWIzYzQgXHViYmY4XHViOWNjXHVjNzc4LCBcdWJjYzBcdWM3NzQgM1x1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NzggXHViM2M0XHVkNjE1XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0IFx1YmNmY1x1Yjg1ZCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YmNmY1x1Yjg1ZCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwXHVkNTU4XHViMjk0IFx1YzljMVx1YzEyMFx1Yzc0NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjODA4XHViMmU4XHVjMTIwXHVjNzc0XHViNzdjXHVhY2UwIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHViZDg0XHVkNTYwXHViNDFjIFx1YmNmY1x1Yjg1ZFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWI0MWMgXHVjMGJjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzQwIFx1YjBiNFx1YmQ4MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGM5XHVjMGMxIEM8c3ViPmk8XC9zdWI+XHViODVjIFx1Y2U2MFx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM3NTggXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjODEwIFx1YzMwZFx1Yzc3NCwgXHViMmU0XHViOTc4IFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjBcdWI0MThcdWIyOTQgXHVjNzdjXHVjNzc0IFx1YzVjNlx1YjNjNFx1Yjg1ZCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YzgwOFx1YjJlOFx1YzEyMFx1Yzc0NCBcdWFkZjhcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWJhODdcdWFjMWNcdWM3NTggXHVjODA4XHViMmU4XHVjMTIwXHVjNzQ0IFx1YWRmOFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjODE1XHVjODEwIFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmx0Oz0gbiAmbHQ7PSAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgbi0yXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWJkODRcdWQ1NjBcdWI0MWMgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWIxMjQgXHVjODE1XHVjMjE4IGEgYiBjIGQgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljNCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YzgxNVx1YzgxMCBhLCBiLCBjXHViOTdjIFx1YzEzOCZuYnNwO1x1YWYyZFx1YzljMFx1YzgxMFx1YzczY1x1Yjg1YyBcdWQ1NThcdWJhNzAsIFx1YjBiNFx1YmQ4MFx1YWMwMCBkXHViNzdjXHViMjk0IFx1YzBjOVx1YzBjMVx1YzczY1x1Yjg1YyBcdWNlNjBcdWQ1NzRcdWM4MzggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gKDEgJmx0Oz0gYSwgYiwgYywgZCAmbHQ7PSBuKTxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YmQ4NFx1ZDU2MFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWIzMDBcdWM3NTggXHVjODA4XHViMmU4XHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM1MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyaWFuZ3VsYXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJpYW5ndWxhdGlvbiBvZiBhIHBvbHlnb24gaXMgYSBzZXQgb2YgdHJpYW5nbGVzIHdpdGggdmVydGljZXMgYXQgdGhlIHZlcnRpY2VzIG9mIGEgcG9seWdvbi4gVGhlc2UgdHJpYW5nbGVzIG11c3Qgbm90IG92ZXJsYXAgYW5kIG11c3QgY292ZXIgdGhlIHdob2xlIHBvbHlnb24uPFwvcD5cclxuXHJcbjxwPldlIGRlZmluZSBhIHBvbHlnb24gY3V0IGFzIGEgc3RyYWlnaHQgbGluZSBzZXBhcmF0aW5nIHRoZSBwb2x5Z29uIGludG8gdHdvIHBpZWNlcy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSB0cmlhbmd1bGF0ZWQgY29udmV4IHBvbHlnb24sIHdoZXJlIGVhY2ggdHJpYW5nbGUgaGFzIHNvbWUgY29sb3IsIGZpbmQgdGhlIG1heGltYWwgbnVtYmVyIG9mIGN1dHMgb25lIGNhbiBkbyBzbyB0aGF0IG5vIHR3byBwb2ludHMgb2YgdGhlIHNhbWUgY29sb3IgZW5kIHVwIGluIHR3byBkaWZmZXJlbnQgcGllY2VzLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8zMzUxXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyMHB4OyB3aWR0aDo0NzRweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcywgbiAoMyAmbGU7IG4gJmxlOyAxMDAsMDAwKS4gVmVydGljZXMgYXJlIG51bWJlcmVkIHdpdGggdW5pcXVlIGludGVnZXJzIGJldHdlZW4gMSBhbmQgbi4gRWFjaCBvZiB0aGUgbmV4dCBuICZtaW51czsgMiBsaW5lcyBjb250YWlucyBmb3VyIGludGVnZXIgbnVtYmVycyBhLCBiLCBjIGFuZCBkICgxICZsZTsgYSxiLGMsZCAmbGU7IG4pLCBtZWFuaW5nIHRoYXQgdGhlIHRyaWFuZ2xlIHdoaWNoIGhhcyBpdHMgdmVydGljZXMgaW4gYSwgYiBhbmQgYyBoYXMgdGhlIGNvbG9yIGQuIGEsIGIgYW5kIGMgYXJlIHRocmVlIGRpZmZlcmVudCB2ZXJ0aWNlcy4gVGhlIGlucHV0IGFsd2F5cyBjb250YWlucyBkYXRhIGFib3V0IGEgcHJvcGVyIHRyaWFuZ3VsYXRpb24gb2YgYSBwb2x5Z29uIGFuZCBhbGwgdHJpYW5nbGVzIGFyZSBjb2xvcmVkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIHNob3VsZCB3cml0ZSBvbmUgbGluZSB0byBzdGFuZGFyZCBvdXRwdXQsIGNvbnRhaW5pbmcgb25lIGludGVnZXIgJm1kYXNoOyB0aGUgbWF4aW1hbCBudW1iZXIgb2YgY3V0cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 5번

  • 문제를 번역한 사람: koosaga