NézetNyomtat

Vektorok (Megoldás)
Címkék > Feladat

Vektorok

Adott néhány síkbeli vektor. Döntsük el, hogy van-e köztük $k$, amelyekből zárt törött-vonal készíthető. (Nehezítés: konvex sokszög készíthető.)
Pozitív válasz esetén adjunk példát, a megfelelő vektorok felsorolásával. Ha több megoldás van, adjuk meg azt, amelynek minimális az átmérője. (Az átmérő a két legtávolabbi csúcs távolsága.)

Feladat

Írjunk programot, ami beolvassa a vektorokat és $k$ értékét, majd kiírja a minimális átmérőjű megoldást. Ha nem készíthető zárt töröttvonal (konvex sokszög), akkor azt kell kiírni, hogy "NINCS MEGOLDÁS".

Bemenet

A VEKTOR.BE első sora $n$ és $k$ értékét tartalmazza, szóközzel elválasztva ($10\le n \le 100, 3\le k \le 6$). A következő $n$ sor a vektorokat adja meg, két egész koordinátájukkal. ($-1000\le x, y \le 1000$)

Kimenet

A VEKTOR.KI egyetlen sorába a töröttvonalat alkotó vektorokat kell írni:
(1;3)+(0;2)+(-4;0)+(3;-5)
alakban, vagy a "NINCS MEGOLDÁS" szöveget.

Példa

VEKTOR.BEVEKTOR.KI
10 3
-379 396
943 -755
-686 -893
145 -615
-540 -69
-275 -515
800 0
0 600
-109 -911
-800 -600
(800;0)+(0;600)+(-800;-600)

Tesztadatok