2144번 - 울타리 넘기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 15 | 7 | 6 | 60.000% |
문제
평면상에 N(1≤N≤100)개의 점들이 있다. 당신은 이 점들 중 K(1≤K≤500)개의 점들을 방문하려고 한다. 같은 점을 여러 번 반복할 수 있지만, 한 점을 연속으로 두 번 방문할 수는 없다. 즉, 어느 한 점으로 이동했으면 그 점에서 다른 점으로 이동해야 한다는 것이다. 각각의 점들은 x, y좌표를 가지며, 0≤x, y≤1,000,000을 만족한다.
또한 이 평면에는 F개의 울타리도 있다. 각각의 울타리는 두 점을 잇는 선분으로 표현된다. 이 울타리들끼리는 서로 교차하지 않으며, 각 울타리에는 높이 h(1≤h≤1,000)가 있다. 높이가 h인 울타리를 넘을 때 성공할 확률은 1/h이다.
한 점에서 한 점으로 이동할 때에는 직선으로만 이동한다. 직선으로 이동하는 도중에 울타리를 만나게 된다면 그 울타리를 넘어야 한다. 만약 여러 울타리를 넘게 된다면 이 울타리들을 모두 성공적으로 넘을 확률은, 각각을 성공적으로 넘을 확률들의 곱이 된다. 만약 울타리가 직선 이동 경로 위에 평행하게 존재한다면, 이를 성공적으로 넘을 확률은 1이다. 또, 울타리의 끝 점만을 살짝 스쳐 지나갈 경우는 울타리를 넘을 필요가 없다.
N개의 점들 외에는 별도로 시작점이 하나 있다. 이동할 때에는 이 시작점에서 시작하여 이 시작점에서 끝나야 한다. K개의 점들을 계산할 때에는 이 시작점과 끝점을 제외하고 생각한다. 이 점에서 이동을 시작하여 K개의 점들을 지나고 이 점에서 이동을 끝낼 때, 울타리들을 성공적으로 넘을 확률을 최대로 하여라.
입력
첫째 줄에 다섯 정수 N, K, F, x, y가 주어진다. x, y는 시작점의 좌표이다. 다음 N개의 줄에는 각 점의 좌표가 주어진다. 다음 F개의 줄에는 다섯 개의 정수로 울타리에 대한 정보가 주어진다. 앞의 두 정수는 울타리의 한 끝점이고, 그 다음 두 정수는 다른 한 끝점이고, 마지막 정수는 높이 h이다.
출력
첫째 줄에 최대인 확률을 출력한다. 출력은 %.4e로 하면 된다.
예제 입력 1
3 6 4 1 3 8 2 15 2 8 7 4 1 4 8 4 7 4 9 4 3 10 1 10 3 2 11 4 16 4 6
예제 출력 1
1.3021e-03
출처
Olympiad > USA Computing Olympiad > 2000-2001 Season > USACO Spring 2001 Contest > Green 3번
- 잘못된 데이터를 찾은 사람: jsa3824
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호