Submit | All submissions | Best solutions | Back to list |
ZELC - Электрификация |
В одной далекой Африканской стране мы помогаем проводить электрификацию. Для этого недалеко от побережья каждого города запустили по водоплавающей АЭС и соединили их с ближайшими к ним домами. Цель данного проекта подсоединить к источнику энергии все дома каждого из городов. Каждый дом, подсоединенный к источнику электроэнергии, сам является источником электроэнергии. В некоторых участках местности можно также ставить дешевые деревянные электрические столбы. Однако в стране существует резкая нехватка электрического кабеля, поэтому протянутая электрическая сеть должна иметь минимальную длину. Стоимость столбов несоизмеримо меньше стоимости кабеля, поэтому количество электрических столбов может быть довольно большим.
Входные данные
t – число городов, затем следуют описания каждого из t городов. [t <= 50]
Описание каждого города начинается с числа N - количество домов в городе [3 <= N <= 3000]. Затем следуют ровно N строчек, на каждой из которых заданы два
вещественных числа: x, y - координаты дома. [0.0 <= x, y <= 10000.0]
Выходные данные
Для каждого теста необходимо вывести замкнутую электрическую сеть, т.е. все дома должны быть соединены между собой, либо напрямую, либо через другие дома, либо через электрические столбы. Для каждого теста на первой строчке выведите число M [0 <= M <= N] - количество деревянных электрических столбов. Далее на каждой из следующих M строчек выведите координаты каждого из столбов x, y [0.0 <= x, y <= 10000.0]. Далее выведите число K равное количеству требуемых участков кабеля. [N+M-1 <= K <= (M+N)*(M+N-1)/2]. И на каждой из следующих K строчек выведите два целых числа i, j - индексы соединяемых домов или столбов. Индексы у домов начинаются с 0 и заканчиваются на N-1, индексы столбов начинаются с N и заканчиваются на N+M-1.
Начисление очков
Количество очков, полученное за данную задачу total_score = (200+time)*(score_1+score_2+...score_t)/200. Где score_i - равно длине электрического кабеля потраченного на электрификацию i-го города, а time - время работы программы.
Пример
Входные данные: 1 4 1.0 1.0 1.0 11.0 11.0 1.0 11.0 11.0 Выходные данные: 1 6.0 6.0 4 0 4 1 4 2 4 4 3Начисление очков:
Положим, что программа работала 10 секунд. Длина кабеля score_1 = 20*sqrt(2). В этом случае количество очков полученных за программу будет равно 29.698485
Added by: | Roman Sol |
Date: | 2006-04-12 |
Time limit: | 0.100s |
Source limit: | 60000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Resource: | ZCon 2007 |