낮이 짧아지고 밤이 길어진다면 도로제설에 관심을 가져야 한다. 그런데 도시의 예산 삭감 때문에 단 한 대의 제설차만 운행할 수 있다. 제설차는 한 번 지나갈 때 도로의 한 차선을 제설할 수 있다. 제설차가 모든 도로의 모든 차선을 제설하는 데 걸리는 최소 시간은 얼마일까?
입력
첫 번째 줄에 차고의 좌표를 미터 단위로 나타낸 두 정수 $x,y$가 주어진다. 두 번째 줄부터는 한 줄마다 도로의 시작점과 끝점의 좌표를 미터 단위로 나타낸 네 정수 $x_{start}$, $y_{start}$, $x_{end}$, $y_{end}$가 주어진다. 최대 $100$개의 도로가 주어질 수 있다.
모든 도로는 시작점과 끝점을 직선으로 이으며, 각 방향으로 한 차선씩 두 차선으로 이루어져 있다. 제설차는 모든 교차로나 도로의 끝에서 유턴을 포함해 어느 방향으로든 회전할 수 있다. 제설차는 도로에서 제설할 때는 시속 $20$ km로 운행하며, 이미 제설한 도로에서는 시속 $50$ km로 운행한다. 입력으로 주어진 도로만으로 차고에서 도로의 모든 부분에 도달할 수 있음이 보장된다.
출력
제설차가 차고에서 출발해 모든 도로의 모든 차선을 제설하고 다시 차고로 돌아오는 데 걸리는 최소 시간을 출력한다. 시간과 분을 0으로 시작하지 않는 정수로 ":"으로 구분하여 출력하고, 분은 가장 가까운 정수로 반올림한다.
20210805 2년 전 2
도로제설
문제
낮이 짧아지고 밤이 길어진다면 도로제설에 관심을 가져야 한다. 그런데 도시의 예산 삭감 때문에 단 한 대의 제설차만 운행할 수 있다. 제설차는 한 번 지나갈 때 도로의 한 차선을 제설할 수 있다. 제설차가 모든 도로의 모든 차선을 제설하는 데 걸리는 최소 시간은 얼마일까?
입력
첫 번째 줄에 차고의 좌표를 미터 단위로 나타낸 두 정수 $x,y$가 주어진다.
두 번째 줄부터는 한 줄마다 도로의 시작점과 끝점의 좌표를 미터 단위로 나타낸 네 정수 $x_{start}$, $y_{start}$, $x_{end}$, $y_{end}$가 주어진다.
최대 $100$개의 도로가 주어질 수 있다.
모든 도로는 시작점과 끝점을 직선으로 이으며, 각 방향으로 한 차선씩 두 차선으로 이루어져 있다. 제설차는 모든 교차로나 도로의 끝에서 유턴을 포함해 어느 방향으로든 회전할 수 있다. 제설차는 도로에서 제설할 때는 시속 $20$ km로 운행하며, 이미 제설한 도로에서는 시속 $50$ km로 운행한다. 입력으로 주어진 도로만으로 차고에서 도로의 모든 부분에 도달할 수 있음이 보장된다.
출력
제설차가 차고에서 출발해 모든 도로의 모든 차선을 제설하고 다시 차고로 돌아오는 데 걸리는 최소 시간을 출력한다. 시간과 분을 0으로 시작하지 않는 정수로 ":"으로 구분하여 출력하고, 분은 가장 가까운 정수로 반올림한다.