CF1142C. U2

【题目链接】https://codeforces.com/problemset/problem/1142/C

【题解】

考虑如何处理在抛物线内部。显然不好处理。

观察式子 $y=x^2+bx+c$，我们发现 $b$ 与 $x^2$ 无关。换句话说，最高只有一次项系数不确定。

因此可以考虑进行转化。令 $y'=y-x^2$，则要求为在直线 $y'=bx+c$ 上方无其余点。维护凸包即可。

效率 $O(n log n)$。

#include<bits/stdc++.h>
struct Graph
{
    struct Vector
    {
        long long x,y;
        Vector(long long _x=0,long long _y=0){x=_x;y=_y;}
        inline friend Vector operator - ( const Vector &u,const Vector &v ) { return Vector(u.x-v.x,u.y-v.y); }
        inline friend long long operator ^ ( const Vector &u,const Vector &v ) { return u.x*v.y-u.y*v.x; }
    }st[1000000];int tp;
    std::vector<Vector> V,E;
    inline void add ( long long x,long long y ) { V.push_back(Vector(x,y)); }
    inline long long solve ( void )
    {
        std::sort(V.begin(),V.end(),[&](const Vector &u,const Vector &v){return u.x==v.x ? u.y>v.y : u.x>v.x;});
        E.push_back(V[0]);
        for ( int i=1;i<(int)V.size();i++ ) if ( V[i].x!=V[i-1].x ) E.push_back(V[i]);
        for ( auto p:E )
        {
            while ( tp>1 and ((p-st[tp-1])^(st[tp]-st[tp-1]))>=0 ) tp--;
            st[++tp]=p;
        }
        return tp-1;
    }
}G;
signed main()
{
    int n;scanf("%d",&n);
    for ( int i=1,x,y;i<=n;i++ ) scanf("%d%d",&x,&y),G.add(x,y-1LL*x*x);
    return !printf("%lld
",G.solve());
}