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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
struct rec { int x,y,d; };

int n,re,d[4444];
vector <rec> a,b;

bool cmp(rec i,rec j)
{
    return i.d<j.d || (i.d==j.d && (i.y<j.y || (i.y==j.y && i.x<j.x)));
}

double cotan(int x,int y)
{
    int xx=a[0].x, yy=a[0].y;
    if (y==yy) return 27081993;
    return 1.0*(x-xx)/(y-yy);
}

int dist(int x,int y)
{
    int xx=a[0].x, yy=a[0].y;
    return (x-xx)*(x-xx)+(y-yy)*(y-yy);
}

bool cmpp(rec i,rec j)
{
    double ii=cotan(i.x,i.y), jj=cotan(j.x,j.y);
    int id=dist(i.x,i.y), jd=dist(j.x,j.y);
    return ii>jj || (ii==jj && id>jd);
}

int area(rec i,rec j,rec k)
{
    int s=(j.x-i.x)*(j.y+i.y)+(k.x-j.x)*(k.y+j.y)+(i.x-k.x)*(i.y+k.y);
    return s;
}

int main()
{
    int i,j;
    rec u;
    cin >> n;
    fr(i,1,n) 
    {
        u.d=0;
        scanf("%d%d",&u.x,&u.y); 
        a.push_back(u);
    }
    while (1)
    {
        sort(a.begin(),a.end(),cmp);
        fr(n,0,int(a.size())-1)
            if (a[n].d) break;
        if (n<3) break;
        a.resize(n);
        sort(a.begin()+1,a.end(),cmpp);
        b.clear();
        b.push_back(a[0]);
        a[0].d=1; b[0].d=0;
        fr(j,1,n-1)
            if (a[j].x!=a[0].x || a[j].y!=a[0].y) break;
        if (j==n) break;
        b.push_back(a[j]);
        a[j].d=1; b[1].d=j;
        fr(i,j+1,n-1)
        {
            while (b.size()>1 && area(a[i],b[b.size()-1],b[b.size()-2])<=0) 
            {
                a[b[b.size()-1].d].d=0;
                b.pop_back();
            }
            b.push_back(a[i]); 
            a[i].d=1; b[b.size()-1].d=i;
        }
        if (b.size()>2) re++;
        int m=b.size();
        fr(i,1,n-1)
        {
            if (cotan(a[i].x,a[i].y)==cotan(b[1].x,b[1].y)) a[i].d=1;
            if (cotan(a[i].x,a[i].y)==cotan(b[m-1].x,b[m-1].y)) a[i].d=1;
        }
        fr(i,1,m-2)
        {
            int l=b[i].d, r=b[i+1].d;
            fr(j,l+1,r-1)
                if (!area(b[i+1],a[j],b[i])) a[j].d=1;
        }
    }
    cout << re << endl;
    return 0;   
}

Code mẫu của ladpro98

#include <iostream>
#include <algorithm>
#include <cstdio>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 4004;
using namespace std;

int n, res;
ii O;
ii a[N]; int s[N];
bool chk[N];

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

void Hull() {
    int i, k, t;
    k = 1;
    for(i = 1; i <= n; i++) {
        while (k > 2 && CCW(a[s[k - 2]], a[s[k - 1]], a[i])) k--;
        s[k++] = i;
    }
    for(i = n, t = k + 1; i; i--) {
        while (k > t && CCW(a[s[k - 2]], a[s[k - 1]], a[i])) k--;
        s[k++] = i;
    }
    for(i = 1; i <= n; i++) chk[i] = false;
    for(i = 1; i < k; i++) chk[s[i]] = true;
    int m = 0;
    for(i = 1; i <= n ; i++) if (!chk[i])
        a[++m] = a[i];
    n = m;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].X, &a[i].Y);
    sort(a + 1, a + 1 + n);
    while (n > 2) {res++; Hull();}
    printf("%d", res);
    return 0;
}

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R+,Q+}
PROGRAM MILITARY;
CONST
  fi='';
  fo='';
  maxn=4000;
  esp=0.000001;
TYPE
  rec=record x,y:real; ind:integer; end;
VAR
  n,c,m,kq:integer;
  a,b:array[1..maxn] of rec;
Procedure ReadInput;
Var
  f:text;
  i:integer;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,n);
  For i:=1 to n do
  with a[i] do
    begin
      Readln(f,x,y);
      ind:=i;
    end;
  Close(f);
End;
Procedure WriteOutput;
Var
  f:text;
Begin
  Assign(f,fo); Rewrite(f);
  Writeln(f,kq);
  Close(f);
End;
Procedure Swap(var p1,p2:rec);
Var
  temp:rec;
Begin
  temp:=p1; p1:=p2; p2:=temp;
End;
Function CCW(p1,p2,p3:rec):integer;
Var
  t,a1,a2,b1,b2:real;
Begin
  a1:=p2.x-p1.x;
  b1:=p2.y-p1.y;
  a2:=p3.x-p2.x;
  b2:=p3.y-p2.y;
  t:=a1*b2-a2*b1;
  If abs(t)<esp then CCW:=0
  else if t<0 then CCW:=-1
  else CCW:=1;
End;
Function Lower(p1,p2:rec):boolean;
Var
  t,a1,a2,b1,b2:real;
Begin
  a1:=p1.x-a[1].x;
  b1:=p1.y-a[1].y;
  a2:=p2.x-a[1].x;
  b2:=p2.y-a[1].y;
  t:=a1*b2-a2*b1;
  Lower:=false;
  If (t>esp) then Lower:=true
  else If (abs(t)<esp) and ((p1.x<p2.x) or ((p1.x=p2.x) and (p1.y<p2.y)))
       then Lower:=true;
End;
Procedure Find;
Var
  i:integer;
Begin
  c:=1;
  For i:=2 to n do
    If (a[i].y<a[c].y) or ((a[i].y=a[c].y) and (a[i].x<a[c].x)) then
      c:=i;
End;
Procedure QuickSort;
  Procedure Sort(l,r:integer);
  Var
    i,j:integer;
    x:rec;
  Begin
    i:=l; j:=r; x:=a[(l+r) div 2];
    repeat
      while lower(a[i],x) do inc(i);
      while lower(x,a[j]) do dec(j);
      if i<=j then
        begin
          Swap(a[i],a[j]);
          inc(i); dec(j);
        end;
    until i>j;
    if i<r then Sort(i,r);
    if l<j then Sort(l,j);
  End;
Begin
  If n>2 then Sort(2,n);
End;
Procedure Graham;
Var
  i:integer;
Begin
  m:=2; b[1]:=a[1]; b[2]:=a[2];
  b[1].ind:=1; b[2].ind:=2;
  For i:=3 to n do
    begin
      while (m>1) and (CCW(b[m-1],b[m],a[i])=-1) do dec(m);
      inc(m);
      b[m]:=a[i];
      b[m].ind:=i;
    end;
End;
Procedure Kt;
Var
  i:integer;
  mm:integer;
Begin
  mm:=m; m:=2;
  For i:=3 to mm do
    begin
      while (m>1) and (CCW(b[m-1],b[m],b[i])<>1) do dec(m);
      inc(m);
      b[m]:=b[i];
    end;
End;
Procedure LoaiDiem;
Var
  i,j:integer;
  n1:integer;
Begin
  For i:=1 to m do
    a[b[i].ind].ind:=-1;
  i:=1; j:=1; n1:=0;
  repeat
    while a[j].ind=-1 do inc(j);
    if j<n then
      begin
        a[i]:=a[j];
        inc(n1);
        inc(i); inc(j);
      end;
  until j>=n;
  n:=n1;
End;
Procedure Solve;
Begin
  kq:=0;
  repeat
    Find;
    Swap(a[c],a[1]);
    QuickSort;
    Graham;
    LoaiDiem;
    Kt;
    If m>2 then inc(kq)
    else exit;
  until m<=2;
End;
BEGIN
  ReadInput;
  Solve;
  WriteOutput;
END.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>

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(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int 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))

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> 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> 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 = (int) 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;
}

typedef pair<int, int> II;
const ld PI = acos(-1.0);
const ld eps = 1e-12;
const int dr[] = { -1, 0, +1, 0};
const int dc[] = { 0, +1, 0, -1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e16 + 5;
const int mod = (ll) (1e9 + eps);

using namespace std;
#define maxn 4005

int cmp(ld a, ld b) {
    if (abs(a - b) < eps) return 0;
    return a > b ? 1 : -1;
}


struct Point {
    ld x, y;
    Point(){};
    Point(ld _x, ld _y){
        x = _x; y = _y;
    }
    bool operator ==(const Point& that) const {
        return (cmp(x, that.x) == 0 && cmp(y, that.y) == 0);
    }
    bool operator <(const Point& that) const {
        if (cmp(x, that.x) != 0) return cmp(x, that.x) < 0;
        return cmp(y, that.y) < 0;
    }
};

int ccw(Point p0, Point p1, Point p2) {
    ld dx1 = p1.x - p0.x, dy1 = p1.y - p0.y;
    ld dx2 = p2.x - p0.x, dy2 = p2.y - p0.y;
    return cmp(dx1 * dy2 - dx2 * dy1, 0);
}

Point O;

ld sqrdist(Point P0, Point P1){
    return sqr(P0.x - P1.x) + sqr(P0.y - P1.y);
}

bool cmp_angle(Point P1, Point P2) {
    int ret = ccw(O, P1, P2);
    if (ret != 0) return ret > 0;
    return sqrdist(O, P1) < sqrdist(O, P2);
}

int convex_hull(Point a[], int &n) {
    if (n <= 2) {
        return 0;
    }

    Point b[maxn];
    int run = 0;

    int imin = 0;
    Rep(i, n) if (a[i].y < a[imin].y || (a[i].y == a[imin].y && a[i].x < a[imin].x)) imin = i;

    swap(a[imin], a[0]);
    O = Point(a[0]);
    sort(a + 1, a + n, cmp_angle);

//    Rep(i, n) cout << a[i].x << " " << a[i].y << endl;

    int m = 2;
    For(i, 2, n - 1) {
        while (m > 1 && ccw(a[i], a[m - 1], a[m - 2]) > 0){
            --m;
            b[run++] = a[m];
        }
        swap(a[m], a[i]);
        ++m;
    }

    int ret = 0;

    Rep(i, run){
        if(ccw(a[0], a[m - 1], b[i]) != 0){
            b[ret++] = b[i];
        }
    }

    Rep(i, ret) a[i] = b[i];
    return n = ret;
}

Point A[maxn];
int n, m;

int main(){
//  freopen("in.txt", "r", stdin);
    cin >> n;
    Rep(i, n) cin >> A[i].x >> A[i].y;

    int res = 0;
    while(true){
        m = n;
        if(convex_hull(A, n) > m - 3) break;
        else res++;
//      Rep(i, n) cout << A[i].x << " " << A[i].y << endl;
    }

    cout << res << endl;
}