Browse
Национална Олимпиада по Информатика, 2012, Кръг 3
Time Limit: 0.7s, Memory Limit: 64MiB
Ели и овчиците й отново са в беда. След като бяха пренесени на другия бряг на реката при безкрайните сочни ливади, дойде моментът те да бъдат прибрани в кошари, за да прекарат нощта в безопасност. Размерите на кошарите са ограничени – във всяка от тях могат да се поберат по не повече от K овчици. Някои от тях може да останат полу- или изцяло празни – това не е проблем – важното е всяка овчица да е под покрив.

Овцете ще бъдат представени като N точки, а кошарите – като M точки с целочислени координати в равнината (полето). Възможно е няколко овце, няколко кошари или няколко овце и няколко кошари да имат едни и същи координати.

Животинките на Ели изминават по единица разстояние за секунда. Тоест ако например някоя от тях е с координати (0, 0) и иска да отиде в кошара с координати (1, 3), то за целта ще са й нужни приблизително 3.16227766 секунди. Ако пък кошарата беше на позиция (3, 4), на овчицата щяха да са нужни 5 секунди. Помогнете на Ели да изчисли за колко най-малко време може всички овце да бъдат прибрани. Овцете могат да се движат едновременно, като можете да считате, че не си пречат една на друга при движението.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, M и K – съответно броят овце, броят кошари и максималният брой овце, които могат да се поберат в една кошара. На следващите N реда ще бъде зададена по една двойка цели числа Xi Yi, описващи координатите на овцете. След тях следват M реда, на които отново ще бъде зададена по една двойка цели числа Xi Yi, които пък задават координатите на кошарите.
Изход
На единствен ред на стандартния изход изведете едно реално число – минималното необходимо време, за което всички овчици могат да стигнат до кошари, без те да се препълват (тоест всяка от тях да съдържа по K или по-малко овце). Тестовете са такива, че това винаги ще е възможно. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N, M, K ≤ 500
  • NM * K
  • -1000 ≤ Xi, Yi ≤ 1000
Примерен Вход Примерен Изход
5 3 2 2 13 9 6 4 8 13 7 11 3 2 11 10 6 4 12 7.810249676
Един от оптималните отговори се получава ако овцете с координати (2, 13) и (4, 8) отидат в кошарата с координати (2, 11), (9, 6) отиде в (4, 12), а (11, 3) и (13, 7) отидат в (10, 6). Забележете, че бихме получили по-малък отговор, ако (9, 6) също отиде в (10, 6), но тогава кошарата би се препълнила (с 3 овце, при максимални 2), което не е позволено. Разстоянието от (9, 6) до (4, 12) e 7.810249675906654.
Мрън!