Þér eru gefnir $N$ punktar á tvívíðu plani. Hnit $i$-ta punktsins eru $(x_i, y_i)$. Þú munt merkja nokkra af þessum $N$ punktum þannig að eftirfarandi skilyrði sé uppfyllt:

• Enginn kúptur ferhyrningur er til þannig að allir fjórir ólíku hornpunktar hans séu meðal merktu punktanna.

Finndu mesta mögulega fjölda merktra punkta.

Skilgreining á kúptum ferhyrningi

Ferhyrningur sem myndaður er af fjórum ólíkum punktum á plani er kúptur ferhyrningur ef hann uppfyllir öll eftirfarandi skilyrði:

• Engir þrír hornpunktar liggja á sömu línu.
• Óaðlægar brúnir eiga engan sameiginlegan punkt.
• Hvert innra horn ferhyrningsins er strangt minna en $180$ gráður.

Inntak

Inntakið er gefið á eftirfarandi sniði:

$$\begin{aligned} &N \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_N \ y_N \end{aligned}$$

• Öll inntaksgildi eru heiltölur.
• $4 \le N \le 500$
• $|x_i|, |y_i| \le 10^8$
• $(x_i, y_i) \ne (x_j, y_j)$ fyrir $i \ne j$.

Úttak

Prentaðu svarið á einni línu.

Dæmi

Inntak 1

5
0 0
-1 0
0 -1
1 0
0 1

Úttak 1

4

Inntak 2

5
0 0
1 1
2 2
2 3
3 2

Úttak 2

5

Inntak 3

7
-1 8
11 8
-4 -2
19 12
-8 -6
7 6
-1 2

Úttak 3

6

Inntak 4

4
0 0
2 0
1 -1
0 1

Úttak 4

3

Athugasemd

Í fyrsta dæminu getur þú merkt fjóra punkta að undanskildum $(-1, 0)$. Ef þú merkir alla punktana er til kúptur ferhyrningur sem hefur hornpunktana fjóra að undanskildum $(0, 0)$, sem brýtur skilyrðið.