10756번 - 편식 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 219 | 46 | 40 | 23.392% |
문제
병찬이는 친구 공찬이를 위해 맛있는 피자를 시켰다. 하지만 공찬이는 올리브를 싫어해서 피자를 잘라서 먹으려고 한다.
병찬이가 갖고 온 피자는 볼록다각형 모양을 하고 있으며, 올리브는 피자 안에 박혀있다. 공찬이는 피자를 보다 편하게 자르기 위해 인접하지 않은 두 꼭짓점을 선택하여 그 두 꼭짓점을 잇는 직선을 따라 피자를 자른다. 공찬이는 잘린 피자의 두 조각 중 올리브가 없는 쪽을 선택해서 먹을 것이다. 다만, 공찬이가 자르는 직선 위에 올리브가 있는 경우 올리브가 두 갈래로 잘리므로 두 조각 모두 먹지 못한다.
이 그림은 첫 번째 예제의 피자 모양이다. 공찬이가 자른 흔적이 점선으로 남아있다.
병찬이는 피자를 많이 먹지 않기 때문에 공찬이는 자신이 먹을 부분이 최대한 크게 피자를 자르려고 한다. 공찬이를 도와 얼마나 피자를 크게 자를 수 있는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 피자의 꼭짓점의 수 N이 주어진다.
두 번째 줄부터 N개의 줄에는 피자의 각 꼭짓점의 좌표 Xi, Yi가 주어진다. 피자의 꼭짓점은 시계 반대 방향으로 주어진다. 피자에서 만들어지는 N개의 각들은 전부 180도보다 작다.
N+2번째 줄에는 올리브의 수 M이 주어진다.
N+3번째 줄부터 M개의 줄에는 올리브의 좌표 Xi, Yi가 주어진다. 올리브가 피자의 변 위에 있거나 피자 밖에 있는 경우는 존재하지 않으며, 올리브는 매우 작아서 점으로 간주해도 상관없다.
출력
만약 공찬이가 피자를 어떻게 자르더라도 두 조각 모두 올리브가 있는 경우 0을 출력한다.
그렇지 않은 경우 공찬이가 먹을 수 있는 피자의 최대 넓이를 2로 곱한 값을 출력한다. 잘 생각해보면, 답은 항상 정수임을 알 수 있다.
제한
모든 좌표는 [-109, 109] 범위에 있다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | 4 ≤ N ≤ 300, 1 ≤ M ≤ 300 |
| 2 | 39 | 4 ≤ N ≤ 3 000, 1 ≤ M ≤ 3 000 |
| 3 | 49 | 4 ≤ N ≤ 300 000, 1 ≤ M ≤ 300 000 |
예제 입력 1
5 0 1 3 0 4 2 2 3 0 3 3 2 1 3 1 3 2
예제 출력 1
4
예제 입력 2
6 -3 3 -3 -4 -2 -5 2 -5 3 -4 3 3 7 1 0 0 -1 0 -3 2 0 0 0 0 2 -1 0
예제 출력 2
10
예제 입력 3
6 0 3 -1 2 -1 -2 0 -3 1 -2 1 2 1 0 0
예제 출력 3
4
힌트
예제 2 설명: 공찬이는 피자의 2번 점과 5번 점을 잇는 직선을 따라 피자를 자르면 된다.
예제 3 설명: 공찬이는 피자의 1번 점과 3번 점을 잇는 직선을 따라 피자를 자르면 된다.
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2015 > Croatian Olympiad in Informatics 2015 4번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호