Pitici2

Rezolvarea optima ruleaza in timp liniar: Daca toate punctele se afla pe o singura dreapta, problema devine triviala. In caz contrar putem gasi trei puncte necolineare, sa le notam cu A, B si C.
Avem doua cazuri:

  • Dreptele AB, BC si AC acopera toate punctele: am obtinut solutia.
  • Exista un punct D, care nu este acoperit de niciuna dintre dreptele de mai sus. Daca exista trei drepte, care acopera toata multimea de puncte, putem avea doua cazuri:
    • Doua drepte acopera cate doua puncte din A, B, C si D, iar a treia acopera alte puncte. Pentru verificarea acestui caz incercam toate cele trei imperecheri posibile (AB+CD,AC+BD,AD+BC).
    • O dreapta acopera doua puncte din A, B, C si D, iar doua trec prin cate un punct din cele ramase. Acest caz se trateaza in felul urmator: sa consideram o anumita imperechere, care defineste doua drepte, de exemplu AB+CD. Daca punctele neacoperite de aceste doua drepte nu sunt colineare, sa consideram un punct E, care nu se afla pe cele doua drepte. Daca multimea de puncte se poate acoperi cu trei drepte, punctul E trebuie sa se afle pe una din ele. Stiind ca E nu se afla pe AB, incercam variantele AB+CE si AB+DE. Pentru celelalte imperecheri procedam in mod simetric.