1860번 - 거미줄 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 177 | 5 | 4 | 18.182% |
문제
동주는 매우 훌륭한 예술가이다. 동주는 크고 훌륭한 예술 작품을 만들기를 매우 좋아한다. 그러던 어는 날 동주는 자신의 논에 큰 거미줄 모양의 예술작품을 만들 계획을 세웠다.
동주의 계획은 다음과 같다. 먼저 자신의 논에 N개의 기둥을 세워 커다란 볼록 다각형을 만든 후, 두 기둥에 줄을 연결한다. 그런데 줄을 연결하는데 제약 조건이 있다. 먼저 좀 더 훌륭한 예술 작품이 나오기 위해서 이웃한 두 개의 기둥에는 줄을 연결할 수가 없다. 그리고 줄이 서로 교차하게 되면 나중에 해체할 때 힘들기 때문에 줄이 서로 교차하는 일은 없어야 한다.
그리고 한 가지의 큰 문제점이 있다. 동주의 논은 매우 오랜 시간동안 관리를 하지 않았기 때문에 반지름이 R인 원 모양의 물웅덩이가 G개 있다. 물웅덩이 위로 줄을 연결하는 일은 매우 힘든 일이므로 물웅덩이 위로 줄이 연결되는 일은 없어야 한다. (물웅덩이의 경계를 지나는 경우도 허용되지 않는 것으로 한다.)
동주의 목적은 위의 조건을 만족 하면서 줄을 최대한 많이 연결 하는 것이다. 여러분은 동주를 도와 N개의 기둥의 좌표와 물웅덩이의 반지름 R과 G개의 물웅덩이의 중심 좌표가 주어져 있을 때 몇 개의 줄로 연결할 수 있는지 구하는 프로그램을 작성하여야 한다.
입력
첫째 줄에 기둥의 개수 N(1 ≤ N ≤ 150), 웅덩이의 개수 G(0 ≤ G ≤ 100), 웅덩이들의 반지름 R(1 ≤ R ≤ 100,000)이 주어진다. 그리고 두 번째 줄부터 N+1번째 줄까지 기둥의 좌표가 주어진다. 그리고 다음 G개의 줄에 걸쳐 웅덩이의 중심의 좌표가 주어진다. 좌표는 0 이상 1,000,000 이하의 정수이다.
입력으로 주어지는 좌표는 모두 다르다.
출력
첫 줄에 연결할 수 있는 최대 줄의 개수를 출력한다.
예제 입력 1
5 3 1 6 10 10 7 9 1 2 0 0 3 2 2 5 6 8 3
예제 출력 1
1
출처
Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO January 2006 Contest > Gold ?번
- 문제를 번역한 사람: author11
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호