JZOJ5950. 【NOIP2018模拟11.04】虐暴全场

题解

很显然，每个线段与它的$b_i$bi​连起来就是一个凸壳，
所以很自然地想到就是用个栈维护。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ls (x<<1)
#define rs (x<<1|1)
#define M ((l+r)>>1)
#define P putchar
#define db double
using namespace std;
const int N=1000003;
int n,m,nxt[N],ans,id,X[N],y[N];
int z[N],top;
double k[N],b[N];
char ch;
void read(int&n)
{
	for(ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for(n=0;'0'<=ch && ch<='9';ch=getchar())n=(n<<1)+(n<<3)+ch-48;
}
void write(int x){if(x>9)write(x/10);P(x%10+48);}
int main()
{
	freopen("beatall.in","r",stdin);
	freopen("beatall.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++)
	{
		read(X[i]),read(y[i]);
		ans=i;k[i]=0;b[i]=y[i];
		for(;top && k[z[top]]*X[i]+b[z[top]]-y[i]<=0;top--);
		if(top)ans=z[top],k[i]=(db)(y[ans]-y[i])/(X[ans]-X[i]),b[i]=(db)y[i]-k[i]*X[i];
		z[++top]=i;
		write(ans);P('\n');
	}
}