## Editorial for Đa giác

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

uses math;
const maxn=100;
var n,re,i,j,k:longint;
x,y:array[1..maxn] of longint;
f:array[1..maxn,1..maxn] of longint;

function check(i,j,k:longint):boolean;
begin
check:=(x[i]-x[j])*(y[i]+y[j])+(x[j]-x[k])*(y[j]+y[k])+(x[k]-x[i])*(y[i]+y[k])<0;
end;

begin
for i:=1 to n do read(x[i],y[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if y[i]*x[j]>y[j]*x[i] then
begin
k:=x[i]; x[i]:=x[j]; x[j]:=k;
k:=y[i]; y[i]:=y[j]; y[j]:=k;
end;
for i:=2 to n do
for j:=1 to i-1 do
begin
f[i,j]:=3;
for k:=1 to j-1 do
if check(i,j,k) then
f[i,j]:=max(f[i,j],f[j,k]+1);
end;
re:=3;
for i:=2 to n do
for j:=1 to i-1 do
re:=max(re,f[i,j]);
writeln(re);
end.


#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 105;
using namespace std;

void operator -= (ii& A, ii B) {A.X -= B.X; A.Y -= B.Y;}
bool CCW(ii A, ii B, ii C) {C -= B; B -= A; return B.X * C.Y > B.Y * C.X;}

int F[N][N];
int n;
ii a[N];
ii O;

int DP(int i, int j) {
if (F[i][j] > 0) return F[i][j];
F[i][j] = 3;
for(int k = 1; k <= n; k++)
if (k != i && k != j && CCW(a[k], a[j], a[i]) && CCW(O, a[k], a[j]))
F[i][j] = max(F[i][j], DP(j, k) + 1);
return F[i][j];
}

int main()
{
scanf("%d", &n);
int i, j, res = 0;
for(i = 1; i <= n; i++) scanf("%d %d", &a[i].X, &a[i].Y);
O = ii(0, 0);
for(i = 1; i <= n; i++) for(j = 1; j <= n; j++)
if (i != j && CCW(O, a[j], a[i])) res = max(res, DP(i, j));
printf("%d", res);
return 0;
}


#### Code mẫu của RR

program NKPOLI;
uses
math;
const
FINP='';
FOUT='';
MAXN=101;
eps=1e-9;
var
x,y:array[0..MAXN] of longint;
c:array[0..MAXN] of real;
d:array[0..MAXN,0..MAXN] of longint;
n:longint;
procedure inp;
var
f:text;
i:longint;
begin
assign(f,FINP); reset(f);
x[0]:=0; y[0]:=0;
for i:=1 to n do
begin
c[i]:=y[i]/x[i];
end;
close(f);
end;
procedure ans;
var
f:text;
kq,i,j:longint;
begin
assign(f,FOUT); rewrite(f);
kq:=0;
for i:=1 to n do
for j:=1 to n do
kq:=max(kq,d[i,j]);
writeln(f,kq);
close(f);
end;
procedure swapr(var a,b:real);
var
temp:real;
begin
temp:=a; a:=b; b:=temp;
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
i,j:longint;
mid:real;
begin
mid:=c[(l+r) div 2]; i:=l; j:=r;
repeat
while c[i]<mid do inc(i);
while c[j]>mid do dec(j);
if i<=j then
begin
swapr(c[i],c[j]);
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function CCW(x1,y1,x2,y2,x3,y3:longint):integer;
var
a1,b1,a2,b2:longint;
t:real;
begin
a1:=x2-x1;
b1:=y2-y1;
a2:=x3-x2;
b2:=y3-y2;
t:=a1*b2-a2*b1;
if abs(t)<eps then CCW:=0
else if t<0 then CCW:=-1
else CCW:=1;
end;
procedure solve;
var
i,j,k:longint;
begin
for i:=1 to n do d[0,i]:=2;
for i:=1 to n-1 do
for j:=i+1 to n do
for k:=0 to i-1 do
if CCW(x[i],y[i],x[j],y[j],x[k],y[k])=1 then
d[i,j]:=max(d[i,j],d[k,i]+1);
end;
begin
inp;
sort(1,n);
solve;
ans;
end.


#### Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 105
#define maxe 100005

struct Point{
int x, y;
Point(){};
Point(int _x, int _y){
x = _x; y = _y;
}
bool operator < (const Point &P) const{
if(x * P.y == y * P.x) return x < P.x;
return x * P.y > y * P.x;
}
};

int ccw(Point P0, Point P1, Point P2){
ll dx1 = P1.x - P0.x, dy1 = P1.y - P0.y;
ll dx2 = P2.x - P0.x, dy2 = P2.y - P0.y;
ll d = dx1 * dy2 - dx2 * dy1;
if(d == 0) return 0;
return d > 0 ? 1 : -1;
}

Point A[maxn];
int n, f[maxn][maxn];

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
scanf("%d", &n);
A[0] = Point(0, 0);
For(i, 1, n) {
scanf("%d %d", &A[i].x, &A[i].y);
}
n++;
sort(A + 1, A + n);
ms(f, 0);
int res = 0;
For(i, 1, n - 1) f[0][i] = 1;
For(i, 1, n - 1) For(j, i + 1, n) Rep(k, i) if(ccw(A[k], A[i], A[j% n]) == 1){
f[i][j] = max(f[k][i] + 1, f[i][j]);
if(j == n) res = max(res, f[i][j]);
}

cout << res;

}


#### Code mẫu của ll931110

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define pnt pair<int,int>
using namespace std;

pnt a[101];
int n;
int f[105][105];

bool angle_cmp(pnt x,pnt y)
{
double a1 = atan2(1.0 * x.second,1.0 * x.first);
double a2 = atan2(1.0 * y.second,1.0 * y.first);
if (a1 != a2) return a1 < a2;
return (x.first * x.first + x.second * x.second < y.first * y.first + y.second * y.second);
}

bool ccw(int p,int q,int r)
{
int x1 = a[q].first - a[p].first,x2 = a[r].first - a[q].first,y1 = a[q].second - a[p].second,y2 = a[r].second - a[q].second;
return (x1 * y2 - x2 * y1 > 0);
}

int main()
{
//    freopen("poly.in","r",stdin);
//    freopen("poly.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].first, &a[i].second);
sort(a + 1,a + n + 1,angle_cmp);
memset(f,0,sizeof(f));

for (int j = 1; j <= n; j++)
{
f[0][j] = 2;
for (int i = 1; i < j; i++)
for (int k = 0; k < i; k++) if (ccw(k,i,j)) f[i][j] = max(f[i][j],f[k][i] + 1);
}
int best = 2;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) if (ccw(i,j,0)) best = max(best,f[i][j]);
printf("%d\n", best);
}