시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 8 4 3 100.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로 하면 된다.

예제 입력

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.3021e-03

힌트

출처

  • 잘못된 데이터를 찾은 사람: jsa3824