题解

对于 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1​,y1​),(x2​,y2​)确定的抛物线
y 1 = x 1 2 + b × x 1 + c y 2 = x 2 2 + b × x 2 + c y_1=x_1^2+b\times x_1+c \\ y_2=x_2^2+b\times x_2+c y1​=x12​+b×x1​+cy2​=x22​+b×x2​+c
移项后
y 1 − x 1 2 = b × x 1 + c y 2 − x 2 2 = b × x 2 + c y_1-x_1^2=b\times x_1+c \\ y_2-x_2^2=b\times x_2+c y1​−x12​=b×x1​+cy2​−x22​=b×x2​+c

令 z i = y i − x i 2 z_i=y_i-x_i^2 zi​=yi​−xi2​，得
z 1 = b × x 1 + c z 2 = b × x 2 + c z_1=b\times x_1+c \\ z_2=b\times x_2+c z1​=b×x1​+cz2​=b×x2​+c
可以解出直线
z = b × x + c z=b\times x+c z=b×x+c
若点 ( x ′ , y ′ ) (x',y') (x′,y′)在抛物线内部，一定满足
y ′ − x ′ 2 > b × x ′ + c y'-x'^2>b\times x'+c y′−x′2>b×x′+c
即点 ( x , y ) (x,y) (x,y) 在直线 z = b × x + c z=b\times x+c z=b×x+c上方
问题转化为，在 n n n个点 ( x i , y i − x i 2 ) (x_i,y_i-x_i^2) (xi​,yi​−xi2​)中，链接若干个点，使得所有点都在直线的下方，思考后发现，就是找凸包的上半部分

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;
struct Point
{
    LL x,y;
    bool operator < (const Point &a)const
    {return (x-a.x)<0 || ((x-a.x)==0 && (y-a.y)<0);}
    Point(LL x=0,LL y=0):x(x),y(y){ }
}a[N],b[N];
typedef Point Vector;
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
LL Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉积
//凸包
/*************************************************************** * 输入点数组p， 个数为p， 输出点数组ch。 返回凸包顶点数 * 希望凸包的边上有输入点，把两个<= 改成 < * 高精度要求时建议用比较 * 输入点不能有重复点。函数执行完以后输入点的顺序被破坏 ****************************************************************/
int ConvexHull(Point *p, int n, Point* ch) {
    sort(p, p+n);      //先比较x坐标，再比较y坐标
    int m = 0;
    for(int i = 0; i < n; i++) {
        while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) >= 0) m--;
        ch[m++] = p[i];
    }
    return m;
}

int main()
{
	int n;
	sc(n);
	for (int i=0;i<n;i++){
		LL x,y;
		scanf("%I64d%I64d",&x,&y); a[i]=Point(x,y-x*x);
	}
	int t=ConvexHull(a,n,b);
	if (b[0].x==b[1].x) t--;
	cout<<t-1;
}