GPLT L3-009. 长城 凸包

题目链接戳这里
像是单纯求凸包,其实不然. 题目的数据,并非题目所画的例子,我画了出来:

数据的图

其实题目是求:求凸包的过程中,那些凸起来的点.
如这个例图中我标记的红色的点.
关于凸包,可以参考我的这篇文章

具体做法:
我们用栈来维护求凸包过程中遇到的点,对于求取过程中,从先到后,点为p[s[k-2]], p[s[k-1]], p[i],其中i是经过计算后使得满足凸性的点,那么中间的p[s[k-1]]点必然是求凸包过程中凸起来的点,我们对其进行一个vis的标记,最后统计vis了几个即可.
另外注意要用long long

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> P;
const ll inf = 0x3f3f3f3f, maxN = 100005;
ll N, M, vis[maxN];
P p[maxN];
ll s[maxN];

bool nok(const P& a, const P& b, const P& c) {
    return (b.fi - a.fi) * (b.se - c.se)
        - (b.fi - c.fi) * (b.se - a.se) >= 0;
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%lld", &N);
    rep(i, 0, N)
        scanf("%lld %lld", &p[i].fi, &p[i].se);
    ll k = 0;
    mst(vis, 0);
    rep(i, 0, N) {
        while (k >= 2 && nok(p[s[k - 2]], p[s[k - 1]], p[i]))
            --k;
        if (k >= 1)
            vis[s[k - 1]] = 1;
        s[k++] = i;
    }
    ll ans = 0;
    rep(i, 1, N)
        if (vis[i])
            ++ans;
    printf("%lld", ans);
    return 0;
}