MILITARY - Câu chuyện người lính

Tác giả: ladpro98

Ngôn ngữ: C++

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

Download