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
     read(n);
     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.

Code mẫu của ladpro98

#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);
  readln(f,n);
  x[0]:=0; y[0]:=0;
  for i:=1 to n do
  begin
    readln(f,x[i],y[i]);
    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);      
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.