NKPOLI - Đa giác
Tác giả: ladpro98
Ngôn ngữ: C++
#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;
}