시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 51 3 3 6.818%

문제

콩나무에 비료를 흠뻑 준 경근이는 설레는 마음으로 콩나무가 쓱쓱 자라길 기대했으나 오히려 콩나무들은 썩어가기만 하는 것이었다. 아뿔싸, 경근이는 콩나무에 물주는 것을 잊어버렸던 것이다. 그래서 경근이는 콩나무들에게 수분을 공급해줄 수 있는 설비를 갖춰 이번에야말로 콩나무가 훌륭하게 자랄 수 있도록 도우려 한다.

콩나무는 2차원 평면으로 표현되는 땅 위에 선분들을 따라 심어져 있으며, 선분은 최대 50개가 주어진다. 서로 다른 두 점이 각 선분의 시작점과 끝점으로 주어진다. 경근이는 평면중 최대 한 점을 골라 설치위치로부터 거리가 R이내인 지역의 풀에는 수분이 자동으로 공급되는 스프링클러를 가격 C1에 설치할 수 있다. 스프링클러의 영역 밖에 존재하는 풀들은 수분공급기를 별도로 설치해야 한다. 수분공급기는 직선모양의 1유닛단위로만 판매하며 끊어서 사용할 수 없다. 유닛길이당 가격은 C2이다. 모든 콩나무들에게 빠짐없이 수분을 공급하기 위한 최소 비용을 출력하라.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스에 대해, 첫 줄에는 콩나무 선분의 갯수 N (1 ≤ N ≤ 50), 스프링클러가 물을 줄 수 있는 영역의 반지름 R (0 ≤ R ≤ 15), 스프링클러의 가격 C1 (1 ≤ C1 ≤ 1,000), 그리고 1유닛길이당 수분공급기의 가격 C2 (1 ≤ C2 ≤ 1,000)이 주어진다.

이어서 N줄에 걸쳐 각 선분들의 정보가 입력되며, 선분의 시작 x좌표 xs, 시작 y좌표 ys, 끝 x좌표 xe, 끝 y좌표 ye (0 ≤ xs, ys, xe, ye ≤ 50)가 공백으로 구분되어 주어진다. 시작점과 끝점은 서로 다르다.

모든 선분은 닿거나 겹치지 않으며, 선분 길이의 총 합은 100 이하이다.

모든 입력은 정수이다.

출력

각 테스트 케이스당 한 줄에 모든 콩나무들에게 수분을 공급하기 위해 필요한 최소 비용을 출력한다.

예제 입력

1
2 1 10 20
0 0 0 1
10 0 11 0

예제 출력

30

힌트

출처

Contest > Coder's High > Coder's High 2014 K번

  • 문제를 만든 사람: tae