select


Timp maxim de execuţie/test:
1 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB


Se cunosc coordonatele în plan pentru n puncte. Oricare trei puncte dintre punctele date nu sunt coliniare.

Cerinţă

Scrieţi un program care să determine numărul maxim de puncte ce pot fi alese dintre cele n date astfel încât să constituie vârfurile unui poligon convex.

Date de intrare

Fişierul de intrare select.in conţine pe prima linie numărul natural n reprezentând numărul de puncte date iniţial. Pe fiecare dintre următoarele n linii se află câte două numere reale separate cu un spaţiu, reprezentând coordonatele celor n puncte.

Date de ieşire

Fişierul de ieşire select.out va conţine o singură linie, pe care este scris un singur număr întreg, reprezentând numărul maxim de puncte care pot fi alese dintre cele n date şi care constituie vârfurile unui poligon convex.

Restricţii

  • 3 <= n <= 100
  • Toate coordonatele sunt perechi de numere reale mai mari sau egale cu 0 şi mai mici sau egale ca 1000, cu cel mult trei zecimale
  • Nu există trei sau mai multe puncte coliniare
  • Toate punctele sunt diferite între ele

Exemple

select.in select.out select.in select.out
19
0 0
40 30
1 29
1 3
20 1
28 2
3 8
4 7
38.1 24
37 25
31 29
12 5
13 6
26 5
19 4
27 7
30 10
35 19
7 28
10 7
0 0
6 3
6 6
10 3
10 6
16 0
9.000 15.0
 5
prof. Lucian Ilea
Colegiul Naţional „Emil Racoviţă” Cluj-Napoca
ylucian@yahoo.com