1490 - Musca

Ferma lui Algo arată ca o gospodărie mare, în care îşi găsesc locul multe animale şi sunt cultivate pe suprafeţe întinse legume, cereale şi pomi fructiferi. În acest an, pomii a fost atacaţi de o musculiţă care le distruge fructele. Algo a căutat o soluţie pentru îndepărtarea musculiţelor, dar nu a găsit una eficientă. A observat însă că musculiţele sunt sensibile la fum. Aşa că a construit un dispozitiv alcătuit din două ţevi, cu care poate să tragă în acelaşi timp, pe aceeaşi direcţie, dar în sens invers, două baloane speciale umplute cu fum. La fiecare acţionare a dispozitivului sunt lansate cu aceeaşi viteză cele două baloane, care se sparg şi împrăştie fumul la contactul cu copacul.

Cerința

Deoarece baloanele speciale şi tehnologia lui de a le umple cu fum sunt costisitoare, Algo îşi propune să alunge dăunătorii folosind cât mai eficient resursele. Astfel el vrea să folosească cât mai puţine baloane şi caută posibilitatea de a amplasa dispozitivul într-un punct din fermă care să îi permită trageri eficiente, adică să poată trage în toți pomii din fermă și la fiecare tragere să atingă doi pomi în acelaşi timp.

Determinaţi dacă este posibil să găsească acest punct.

Date de intrare

Fișierul de intrare musca.in conține:

• pe prima linie numărul n de pomi de la fermă;
• pe următoarele n linii coordonatele pomilor în forma abscisă ordonată, separate prin spaţiu.

Date de ieșire

Fișierul de ieșire musca.out va conține pe prima linie numărul 1, dacă există soluţie sau 0 dacă nu există soluţie. În cazul în care există soluţie se vor scrie în continuare, pe aceeaşi linie, separate prin spaţiu, coordonatele punctului determinat, în ordinea abscisă ordonată, ca numere reale cu 3 zecimale exacte.

Restricții și precizări

• 1 ≤ n ≤ 1000
• pomii sunt consideraţi puncte în plan, fără să ţinem cont de grosimea şi înălţimea lor;
• coordonatele punctelor sunt numere întregi din intervalul [-10000, 10000];
• dispozitivul nu poate fi amplasat într-un copac;
• balonul explodează doar la contactul cu pomul.

Exemplu:

musca.in

4
10 0
10 10
0 10
0 0

musca.out

1 5.000 5.000

Explicație

Există un punct în care poate fi amplasat dispozitivul. Acesta se află la coordonatele (5,5).

<syntaxhighlight lang="python" line="1"> import math

n = int(input()) x = [0] * 10000 y = [0] * 100000

for i in range(1, n+1):

   x[i], y[i] = map(int, input().split())

ok = 1 if n % 2 == 1:

   ok = 0

if ok:

   for i in range(1, n):
       for j in range(i+1, n+1):
           if x[i] > x[j]:
               a = x[i]
               x[i] = x[j]
               x[j] = a
               a = y[i]
               y[i] = y[j]
               y[j] = a
           elif x[i] == x[j]:
               if y[i] > y[j]:
                   a = y[i]
                   y[i] = y[j]
                   y[j] = a

   mx = (x[1] + x[n]) / 2.0
   my = (y[1] + y[n]) / 2.0
   print(mx, my)
   for i in range(2, n//2 + 1):
       if (x[i] + x[n+1-i]) / 2.0 != mx or (y[i] + y[n+1-i]) / 2.0 != my:
           ok = 0
       print((x[i] + x[n+1-i]) / 2.0, (y[i] + y[n+1-i]) / 2.0)

if ok:

   print(1, end=)
   m = int(mx * 1000)
   mx = m / 1000.0
   print("{:.3f} {:.3f}".format(mx, my))

else:

   print(0)

</syntaxhighlight>