2006 - Mana

Cerinţa

Înștiințat de atacul orcilor, Gandalf și-a luat măsurile de precauție. Credinciosul spion i-a adus acestuia o hartă care arată pozițiile celor n orci. Harta poate fi reprezentată ca un sistem cartezian de coordonate. Gandalf vrea să folosească o vrajă astfel încât să anihileze cel puțin k orci. De asemenea, acesta vrea să folosească cât mai puțină mana. Știind că, dacă utilizează r mana (r număr natural), și vraja este folosită în punctul de coordonate (x,y), acesta anihilează toți orcii din interiorul cercului cu centrul în (x,y) de rază r, aflați mana minimă necesară pentru a anihila k orci.

Date de intrare

Fișierul de intrare manain.txt conține pe prima linie două numere naturale n, k, cu semnificațiile din enunț. Pe următoarele n linii se găsesc câte două numere întregi separate printr-un spațiu, reprezentând abscisa respectiv ordonata fiecărui orc de pe hartă.

Date de ieșire

Fișierul de ieșire manaout.txt va conține pe prima linie numărul r, reprezentând mana minimă pe care o poate utiliza Gandalf pentru a anihila k orci.

Restricţii şi precizări

• 1 ⩽ k ⩽ n ⩽ 100
• Numerele din fișierul de intrare sunt întregi cuprinse între -100000 și 100000.

Exemplul 1

manain.txt

5 3
3 3
5 3
1 -5
-4 1
0 3

manaout.txt

3

Exemplul 2

manain.txt

5 3
3 3
5 3
1 -5
-4 1
1000001 3

manaout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

from math import sqrt, ceil


def distanta(p1, p2):
    return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)


def mana_minima(n_val, k_val, orci_val):
    if not (1 <= k_val <= n_val <= 100):
        return "Datele de intrare nu corespund restrictiilor impuse"
    if any(abs(orc[0]) > 100000 or abs(orc[1]) > 100000 for orc in orci_val):
        return "Datele de intrare nu corespund restrictiilor impuse"

    distante = []
    for orc in orci_val:
        distante_orc = sorted(distanta(orc, orc2) for orc2 in orci_val)
        distante.append(distante_orc[k_val - 1])
    return ceil(min(distante))


with open('manain.txt', 'r') as fin:
    n, k = map(int, fin.readline().strip().split())
    orci = [list(map(int, line.split())) for line in fin]
    result = mana_minima(n, k, orci)

with open('manaout.txt', 'w') as fout:
    fout.write(str(result))

Explicatie

Gandalf poate să folosească vraja în punctul de abscisă 2,5 și ordonată 3.