3179번 - 삼각형 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 50 | 13 | 11 | 30.556% |
문제
평면 상에 N개의 점이 있다.
여기서 3개의 점을 골라 삼각형을 만들었을 때, 이 삼각형 안에 다른 점들이 최대로 들어가면 이를 슈퍼 삼각형이라고 부른다. 이때, 삼각형의 변이나 꼭짓점에 있는 점들도 삼각형 내부에 있는 것으로 간주한다.
주어진 점들을 가지고 슈퍼 삼각형을 형성하는 세 점을 찾으시오.
입력
첫 번째 줄에는 N(3 ≤ N ≤ 300)이 들어온다.
다음 N개의 줄에는 각 점의 좌표 xi, yi가 들어온다.
단, 주어진 입력에는 평행하지 않은 세 개의 점이 적어도 한 쌍은 있다.
출력
첫 번째 줄에 슈퍼 삼각형 안에 포함되는 점의 개수를 출력한다.
두 번째 줄에 슈퍼 삼각형을 이루는 세 점의 번호를 아무렇게나 출력한다.
예제 입력 1
6 1 3 2 3 2 1 3 1 3 2 4 4
예제 출력 1
5 1 4 6
예제 입력 2
9 1 1 2 2 3 3 2 1 3 2 3 1 4 2 4 1 5 1
예제 출력 2
9 1 9 3
예제 입력 3
13 1 3 2 4 3 1 4 1 4 2 4 3 4 4 4 5 5 1 5 2 6 1 6 5 7 3
예제 출력 3
9 3 11 8
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Croatian Olympiad in Informatics 2006 3번
- 문제를 번역한 사람: luke0201
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호