99727 Do zrobienia dwa zadania w C++ do piątku 25.01.12

Zad 1. Terytorium pewnego państwa jest wielokątem o N bokach (i N wierzchołkach). Parlament uchwalił ustawę, według której państwo ma zostać podzielone na gminy. Każda gmina ma być czworokątem wypukłym. Ze względu na oszczędności budżetowe gmin tych ma być jak najmniej. Przykładowy podział państwa na gminy przedstawiono na poniższym rysunku. Nie wiadomo, czy jest to najlepszy podział. Zadanie Napisz program, który wyznaczy pokrycie N-kąta czworokątami wypukłymi. Rozwiązanie dające najlepsze rezultaty (najmniejszą liczbę gmin) zostanie nagrodzone podwójną liczbą punktów. Wejście Pierwsza linia standardowego wejścia zawiera liczbę całkowitą D (1