Aria unui poligon oarecare (poate fi si concav) cu n varfuri este jumatate din suma de i de la 1 la n din determinant de:
  xi     yi
xi+1 yi+1
unde xi, yi sunt coordonatelor varfului i. Daca i=n in loc de i+1 se ia 1. Pentru ca sa functioneze punctele trebuie sa fie ordonate in sens orar sau trigonometric. Daca punctele sunt date in sens trigonometric aria da negativa si trebuie sa o iei in modul.

dar mai e o problema care inca nu mi-e foarte clara!
cum faci fara backtracking toate posibilitatile de combinare ( ca sa vezi care e mai buna?

Nu faci backtracking, faci dinamica...  

Algoritmul tau e gresit. Incepi bine (ca sa ordonezi punctele faci infasuratoare convexa), dar nu iei in calcul ca diferenta optima poate fi obtinuta si modificand punctele 1-4-6 sa zicem... Nu e obligatoriu sa le iei numai pe cele pare sau pe cele impare. Ca sa afli diferenta optima faci o programare dinamica simpla, fiecare puncte are doua posibilitati, modificat sau nu...
Daca m-as fi gandit asa si azi dimineata...