시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 39 25 14 51.852%

문제

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

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

볼록 다각형이라 함은. 다각형 내부의 내각이 모두 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+XHJcblx0PGxpPlx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMDEgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzBiY1x1YWMwMVx1ZDYxNVx1YjA3Y1x1YjlhY1x1YjI5NCBcdWFjYjlcdWNjZDBcdWMxMWMgXHVjNTQ4XHViNDE4XHViYTcwLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5XHVjNzQwIFx1YjJlNFx1YWMwMVx1ZDYxNVx1YWNmYyBcdWIzZDlcdWM3N2NcdWQ1NThcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1Yjc3YyBcdWQ1NjhcdWM3NDAuIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM3NTggXHViMGI0XHVhYzAxXHVjNzc0IFx1YmFhOFx1YjQ1MCAxODBcdWIzYzQgXHViYmY4XHViOWNjXHVjNzc4LCBcdWJjYzBcdWM3NzQgM1x1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NzggXHViM2M0XHVkNjE1XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0IFx1YmNmY1x1Yjg1ZCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YmNmY1x1Yjg1ZCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwXHVkNTU4XHViMjk0IFx1YzljMVx1YzEyMFx1Yzc0NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVjODA4XHViMmU4XHVjMTIwXHVjNzc0XHViNzdjXHVhY2UwIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHViZDg0XHVkNTYwXHViNDFjIFx1YmNmY1x1Yjg1ZFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWI0MWMgXHVjMGJjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzQwIFx1YjBiNFx1YmQ4MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGM5XHVjMGMxIEM8c3ViPmk8XC9zdWI+XHViODVjIFx1Y2U2MFx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM3NTggXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjODEwIFx1YzMwZFx1Yzc3NCwgXHViMmU0XHViOTc4IFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjBcdWI0MThcdWIyOTQgXHVjNzdjXHVjNzc0IFx1YzVjNlx1YjNjNFx1Yjg1ZCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YzgwOFx1YjJlOFx1YzEyMFx1Yzc0NCBcdWFkZjhcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWJhODdcdWFjMWNcdWM3NTggXHVjODA4XHViMmU4XHVjMTIwXHVjNzQ0IFx1YWRmOFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YzgxNVx1YzgxMCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsdDs9IG4gJmx0Oz0gMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IG4tMlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViZDg0XHVkNTYwXHViNDFjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHViMTI0IFx1YzgxNVx1YzIxOCBhIGIgYyBkIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM4MTVcdWM4MTAgYSwgYiwgY1x1Yjk3YyBcdWMxMzgmbmJzcDtcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNTU4XHViYTcwLCBcdWIwYjRcdWJkODBcdWFjMDAgZFx1Yjc3Y1x1YjI5NCBcdWMwYzlcdWMwYzFcdWM3M2NcdWI4NWMgXHVjZTYwXHVkNTc0XHVjODM4IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuICgxICZsdDs9IGEsIGIsIGMsIGQgJmx0Oz0gbik8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0NCBcdWJkODRcdWQ1NjBcdWQ1NThcdWIyOTQgXHVjZDVjXHViMzAwXHVjNzU4IFx1YzgwOFx1YjJlOFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzNTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmlhbmd1bGF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyaWFuZ3VsYXRpb24gb2YgYSBwb2x5Z29uIGlzIGEgc2V0IG9mIHRyaWFuZ2xlcyB3aXRoIHZlcnRpY2VzIGF0IHRoZSB2ZXJ0aWNlcyBvZiBhIHBvbHlnb24uIFRoZXNlIHRyaWFuZ2xlcyBtdXN0IG5vdCBvdmVybGFwIGFuZCBtdXN0IGNvdmVyIHRoZSB3aG9sZSBwb2x5Z29uLjxcL3A+XHJcblxyXG48cD5XZSBkZWZpbmUgYSBwb2x5Z29uIGN1dCBhcyBhIHN0cmFpZ2h0IGxpbmUgc2VwYXJhdGluZyB0aGUgcG9seWdvbiBpbnRvIHR3byBwaWVjZXMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgdHJpYW5ndWxhdGVkIGNvbnZleCBwb2x5Z29uLCB3aGVyZSBlYWNoIHRyaWFuZ2xlIGhhcyBzb21lIGNvbG9yLCBmaW5kIHRoZSBtYXhpbWFsIG51bWJlciBvZiBjdXRzIG9uZSBjYW4gZG8gc28gdGhhdCBubyB0d28gcG9pbnRzIG9mIHRoZSBzYW1lIGNvbG9yIGVuZCB1cCBpbiB0d28gZGlmZmVyZW50IHBpZWNlcy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMzM1MVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjBweDsgd2lkdGg6NDc0cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdmVydGljZXMsIG4gKDMgJmxlOyBuICZsZTsgMTAwLDAwMCkuIFZlcnRpY2VzIGFyZSBudW1iZXJlZCB3aXRoIHVuaXF1ZSBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIG4uIEVhY2ggb2YgdGhlIG5leHQgbiAmbWludXM7IDIgbGluZXMgY29udGFpbnMgZm91ciBpbnRlZ2VyIG51bWJlcnMgYSwgYiwgYyBhbmQgZCAoMSAmbGU7IGEsYixjLGQgJmxlOyBuKSwgbWVhbmluZyB0aGF0IHRoZSB0cmlhbmdsZSB3aGljaCBoYXMgaXRzIHZlcnRpY2VzIGluIGEsIGIgYW5kIGMgaGFzIHRoZSBjb2xvciBkLiBhLCBiIGFuZCBjIGFyZSB0aHJlZSBkaWZmZXJlbnQgdmVydGljZXMuIFRoZSBpbnB1dCBhbHdheXMgY29udGFpbnMgZGF0YSBhYm91dCBhIHByb3BlciB0cmlhbmd1bGF0aW9uIG9mIGEgcG9seWdvbiBhbmQgYWxsIHRyaWFuZ2xlcyBhcmUgY29sb3JlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgcHJvZ3JhbSBzaG91bGQgd3JpdGUgb25lIGxpbmUgdG8gc3RhbmRhcmQgb3V0cHV0LCBjb250YWluaW5nIG9uZSBpbnRlZ2VyICZtZGFzaDsgdGhlIG1heGltYWwgbnVtYmVyIG9mIGN1dHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 5번

  • 문제를 번역한 사람: koosaga