울타리 넘기

평면 위에 방문할 수 있는 점 N개와 별도의 시작점 하나가 있다. 방문할 수 있는 각 점과 시작점은 좌표 (x, y)로 주어지며, 모든 좌표는 0 <= x, y <= 1,000,000을 만족한다. 당신은 시작점에서 출발해 방문 가능한 점들 중 정확히 K개를 방문한 뒤 다시 시작점으로 돌아와야 한다. 같은 점을 여러 번 방문할 수 있지만, 같은 점을 연속해서 두 번 방문할 수는 없다. 시작점은 이 K번의 방문 횟수에 포함하지 않는다.

평면에는 F개의 울타리도 있다. 각 울타리는 두 끝점을 잇는 선분으로 주어지며, 울타리끼리는 서로 교차하지 않는다. 각 울타리에는 높이 h가 있고, 높이 h인 울타리를 한 번 넘는 데 성공할 확률은 1/h이다.

한 점에서 다른 점으로 이동할 때는 항상 두 점을 잇는 직선 경로로 이동한다. 이동 경로가 울타리를 만나면 그 울타리를 넘어야 하며, 여러 울타리를 만나면 모든 울타리를 넘는 데 성공해야 한다. 따라서 한 이동에서 여러 울타리를 넘을 때의 성공 확률은 각 울타리를 넘는 성공 확률의 곱이다. 이동 경로와 울타리가 평행하게 겹치는 경우 그 울타리는 성공 확률에 영향을 주지 않는다. 또한 이동 경로가 울타리의 끝점만 스쳐 지나가는 경우에는 그 울타리를 넘지 않아도 된다.

정확히 K개의 점을 방문하고 시작점으로 돌아오는 모든 가능한 경로 중에서, 모든 울타리를 성공적으로 넘을 확률의 최댓값을 구하시오.

첫째 줄에 정수 N, K, F, x, y가 주어진다. 여기서 (x, y)는 시작점의 좌표이다. 다음 N개의 줄에는 방문 가능한 각 점의 좌표가 한 줄에 하나씩 주어진다. 그다음 F개의 줄에는 울타리 하나의 정보가 다섯 정수로 주어진다. 앞의 두 정수는 울타리의 한 끝점 좌표, 다음 두 정수는 다른 끝점 좌표, 마지막 정수는 울타리의 높이 h이다.

첫째 줄에 가능한 최대 성공 확률을 출력한다. %.4e 형식으로 출력하면 된다.