시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 66 10 10 24.390%

문제

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

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

그리하여 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만큼 걸린다.

출력

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

예제 입력

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

예제 출력

7.3

힌트

출처

  • 문제를 만든 사람: xhark