Na płaszczyźnie danych jest n parami różnych punktów. Chcemy je obrać jak cebulkę. Jedno obranie, to wybranie kilku punktów, które są wierzchołkami wielokąta wypukłego (możliwe, że zdegenerowanego; ściśle: żaden wierzchołek nie jest we wnętrzu trójkąta o wierzchołkach w trzech innych wybranych punktach) tak, by na zewnątrz tego wielokąta nie było żadnego punktu, po czym wyrzucenie wybranych punktów. Mając danych n punktów, ile minimalnie warstw cebulki trzeba zrobić?
W pierwszej linii wejścia jest liczba 1 <= n <= 1000, oznaczająca liczbę punktów. W każdej kolejnej linii są współrzędne jednego punktu: - 1 000 000 000 <= x,y <= 1 000 000 000. Na wyjściu masz wypisać jedną liczbę, oznaczającą liczbę warstw cebuli do zdjęcia.
Dla takich danych:
6 -10 -10 8 0 0 8 0 0 -1 -1 -2 -2
prawidłową odpowiedzią jest:
2
[Zgłoś rozwiązanie] [Moje zgłoszenia]