시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 111 23 17 26.154%

문제

결국 당신과 옆 나라 왕은 서로 화가 난 나머지 전쟁을 시작할 준비를 하게 된다.

그리하여 옆 나라에 선전포고를 하려 했으나, 당신은 자비로운 왕이었기 때문에 옆 나라에 있는 당신의 백성들을 당신의 국가로 귀환 시킨 후 선전 포고를 하고자 했다.

그리하여 Y년 M월 D일. 미리 옆 나라에 있는 모든 백성들에게 귀환 명령을 내려놓았기 때문에, 그들 모두가 한꺼번에 이동을 시작했다.

옆 나라에는 통과할 수 없는 직선모양의 장애물이 있기 때문에 백성들이 국경을 넘는 시간이 지연될 수 있다.

만약 모든 백성들이 가장 빠른 경로로만 이동해서 국경을 넘는다면, 과연 얼마 후에야 모든 사람들이 국경을 넘을 수 있는지 계산하라.

입력

첫째 줄에는 백성의 명수인 N(1 ≤ N ≤ 50)과, 직선 장애물의 개수 M(1 ≤ M ≤ 50)이 주어진다. 2번째 줄에서 N+1번째 줄에는 백성들의 좌표(x, y)와 속도 v가 주어진다.(1 ≤ x.y ≤ 100, 1 ≤ v ≤ 10, x, y, v는 정수) N+2번째 줄에서 N+M+1번째 줄에는 직선 장애물의 좌표 (x1, y1) - (x2, y2)이 주어진다.(1 ≤ x1, y1, x2, y2 ≤ 100, x1, y1, x2, y2는 정수) 직선 장애물은 서로 교차하지 않는다. 또한, 직선 y=0은 국경이다.

거리 a를 가면서 속도가 v이면 시간은 a/v만큼 걸린다.

출력

모든 백성들이 국경을 넘을 수 있는 최소 시간을 소수점 첫째자리 까지 출력한다.

예제 입력 1

3 3
(2,7) 1
(4,7) 2
(8,4) 1
(0,1) - (4,2)
(5,3) - (7,2)
(3,5) - (6,5)

예제 출력 1

7.3

출처