SP3640 HNSUBWAY - Hanoi Subway System Construction

[English](/problems/HNSUBWAY/en/) [Vietnamese](/problems/HNSUBWAY/vn/)Hanoi is constructing a subway system. The subway system consists of M stations which are numbered from 1 to M and K two-way subway lines connecting pairs of stations directly. Hanoi metropolitan area is covered by T separated resident blocks each described as convex polygons. Subway lines can run under resident blocks. When running under resident blocks including their boundary, the speed of the subway train is v1 while its speed is v2 when running under other parts (v1 < v2). The travel time between two stations a and b is the shortest time to go from a to b, possibly via intermediate stations (the transit time is not significant). They now have to select the central station from those existing stations so that the travel time from the central station to the farthest station, whose travel time to the central station is longest, is shortest. The figure below describes a subway system with four subway stations and four subway lines. There are three resident blocks in the metropolitan area. In this figure, there are two segments of subway lines under resident blocks where the subway train has to travel with speed of v1.  Given a subway system, your task is to write a program to find the central station and to find the travel time from the farthest station to the central station.

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets. For each data set, the first line contains five integers M, K, T, v1, v2 (M < 31, K < 50, T < 10, 0 < v1 < v2 < 100) separated by space indicating number of stations, number of subway lines, number of resident blocks, the subway train speed when travelling under resident blocks, and the subway train speed when not travelling under resident blocks respectively. The ith line of the following M lines contains two integers Xi and Yi (-10000

For each data set, write in one line an integer indicating the integer part of (tmax \* 100) where tmax is the travel time from the farthest station to the central station.