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.