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

Download