Wykres
Limit pamięci: 64 MB
Wykresem nazywamy dowolny ciąg punktów na płaszczyźnie.
Dany wykres zamierzamy zastąpić
innym wykresem, który będzie miał co najwyżej
punktów (
),
ale w taki sposób, aby "przypominał" jak najbardziej oryginalny wykres.
Nowy wykres tworzymy w ten sposób, że dzielimy ciąg punktów na
(
) spójnych podciągów:
przy czym ,
a następnie każdy podciąg
, dla
,
zastępujemy jednym nowym punktem
.
Mówimy wtedy, że każdy z punktów
został ściągnięty do punktu
.
W rezultacie otrzymujemy nowy wykres reprezentowany przez ciąg
.
Miarą podobieństwa tak utworzonego wykresu do oryginalnego jest
maksimum odległości każdego z punktów
do punktu, do którego został on ściągnięty:
przy czym jest odległością między
i
i wyraża się standardowym wzorem:
Przykładowy wykres i nowy wykres
,
gdzie
ściągamy do
, natomiast
do
.
Dla danego wykresu składającego się z punktów należy znaleźć wykres najbardziej go przypominający,
który zawiera co najwyżej
punktów,
przy czym podział wykresu na spójne podciągi jest dowolny.
Ze względu na skończoną precyzję obliczeń, za poprawne będą uznawane wyniki, których podobieństwo
do danego wykresu jest co najwyżej o
większe od optymalnego wyniku.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz
oddzielone pojedynczym odstępem,
.
Każdy z następnych
wierszy zawiera po dwie liczby całkowite oddzielone pojedynczym odstępem.
W
-szym wierszu znajdują się liczby
,
,
reprezentujące współrzędne
punktu
.
Wyjście
W pierwszym wierszu standardowego wyjścia należy wypisać jedną liczbę rzeczywistą , będącą miarą
podobieństwa znalezionego wykresu do wykresu oryginalnego.
W drugim wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą
,
.
Następnie, w kolejnych
wierszach powinny zostać wypisane współrzędne punktów
,
po jednym punkcie w wierszu.
W
-gim wierszu powinny znaleźć się liczby rzeczywiste
i
oddzielone pojedynczym odstępem
i określające współrzędne
punktu
.
Wszystkie liczby rzeczywiste na wyjściu należy wypisać z rozwinięciem do co najwyżej 15 cyfr po kropce dziesiętnej.
Przykład
Dla danych wejściowych:
7 2 2 0 0 4 4 4 4 2 8 2 11 3 14 2
poprawną odpowiedzią jest:
3.00000000 2 2.00000000 1.76393202 11.00000000 1.99998199
Autor zadania: Jakub Pawlewicz.