Codeforces 1142C U2 凸包

题解

对于$(x_1,y_1),(x_2,y_2)$(x1​,y1​),(x2​,y2​)确定的抛物线
$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\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$zi​=yi​−xi2​，得
$z_1=b\times x_1+c \\ z_2=b\times x_2+c$z1​=b×x1​+cz2​=b×x2​+c
可以解出直线
$z=b\times x+c$z=b×x+c
若点$(x',y')$(x′,y′)在抛物线内部，一定满足
$y'-x'^2>b\times x'+c$y′−x′2>b×x′+c
即点$(x,y)$(x,y) 在直线$z=b\times x+c$z=b×x+c上方
问题转化为，在$n$n个点$(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;
}