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;
}

Download