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