3351번 - 삼각 분할 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 136 | 66 | 49 | 46.667% |
문제
계산기하 분야에서 삼각분할은, 다음과 같은 조건을 만족하는 삼각형의 집합을 뜻한다.
- 삼각형의 각 꼭짓점은 다각형에 있는 꼭짓점 중 하나이다.
- 삼각형끼리는 겹쳐서 안되며, 삼각형들의 합집합은 다각형과 동일하다.
볼록 다각형이라 함은. 다각형 내부의 내각이 모두 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
출처
Olympiad > Baltic Olympiad in Informatics > BOI 2009 5번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호