題目鏈接戳這里
像是單純求凸包,其實不然. 題目的數(shù)據(jù),并非題目所畫的例子,我畫了出來:

數(shù)據(jù)的圖

其實題目是求:求凸包的過程中,那些凸起來的點.
如這個例圖中我標(biāo)記的紅色的點.
關(guān)于凸包,可以參考我的這篇文章

具體做法:
我們用棧來維護(hù)求凸包過程中遇到的點,對于求取過程中,從先到后,點為p[s[k-2]], p[s[k-1]], p[i],其中i是經(jīng)過計算后使得滿足凸性的點,那么中間的p[s[k-1]]點必然是求凸包過程中凸起來的點,我們對其進(jìn)行一個vis的標(biāo)記,最后統(tǒng)計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;
}