正题

题目链接:https://www.luogu.com.cn/problem/P3291

题目大意

给出 \(n\) 个数字对 \((atk,dnf)\)，求一个\((a,b)\)。

对于每个数字对可以选择任意一个实数\(k\)让其变为\((atk+k\times a,dnf-k\times a)\)，但是操作完之后两个数字都非负。记\(atk/dnf(a,b)\)表示在\((a,b)\)下\(atk/dnf\)的最大值。

然后要求最小化\(max\{atk_i(a,b),dnf_i(a,b)\}\)。

\(1\leq n\leq 10^6,1\leq atk,dnf\leq 10^8\)

解题思路

首先视\((atk,dnf)\)为一个点的话，那么对于任意一个\((a,b)\)答案肯定是在上凸壳上的。

然后考虑实际上我们并不需要用到\((a,b)\)只需考虑\(\frac{b}{a}\)的值，定义\(k=\frac{b}{a}\)

然后就是要求最小化（用\(a_i\)代\(atk_i\)，\(d_i\)代\(dnf_i\)）

\[a_i+b_i+a_ik+b_i\frac{1}{k}
\]

考虑这个点在\(k\)的哪些区间由它取到最大值，对于一个\(j\)需要满足

\[a_i+b_i+a_ik+b_i\frac{1}{k}>a_j+b_j+a_jk+b_j\frac{1}{k}
\]

化一下

\[(a_i-a_j)k^2+(a_i-a_j+b_i-b_j)k+(b_i-b_j)>0
\]

然后就是一个二次不等式，并且考虑到\(j\)只需考虑凸壳上\(i\)左右连接的两个点，解出来我们可以得到\(k\)的合法范围。

然后上面那个是一个对钩函数，现在只需在这个范围内求这个对钩函数的最小值就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=1e6+10;

struct node{

	double x,y;

}p[N],s[N];

int n,top;double ans;

bool calc(double a,double b,double c,double &l,double &r){

	double d=b*b-4.0*a*c;

	if(d<0)return 0;d=sqrt(d);

	double x0=(-b-d)/(2*a),x1=(-b+d)/(2*a);

	if(x0>x1)swap(x0,x1);l=x0;r=x1;

	return 1;

}

bool cmp(node x,node y)

{return (x.x==y.x)?(x.y>y.y):(x.x<y.x);}

double solpe(node x,node y)

{return (y.y-x.y)/(y.x-x.x);}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lf%lf",&p[i].x,&p[i].y);

	sort(p+1,p+1+n,cmp);

	for(int i=1;i<=n;i++){

		while(top>1&&solpe(s[top-1],s[top])<=solpe(s[top-1],p[i]))top--;

		s[++top]=p[i];

	}

	ans=1e18;

	for(int i=1;i<=top;i++){

		double z=sqrt(s[i].y/s[i].x);

		double l=0,r=1e18,L=1,R=1;bool flag=1;

		if(i>1)calc(s[i].x-s[i-1].x,s[i].x-s[i-1].x+s[i].y-s[i-1].y,s[i].y-s[i-1].y,L,R);

		if(i<top)flag&=calc(s[i].x-s[i+1].x,s[i].x-s[i+1].x+s[i].y-s[i+1].y,s[i].y-s[i+1].y,l,r);

		if(!flag)continue;

		if(L<l)l=max(R,l);if(R>r)r=min(r,L);

		if(l>r||r<=0)continue;z=max(z,l);z=min(z,r);

		if(z>L&&z<R){

			if(L>=l)ans=min(ans,s[i].x+s[i].y+s[i].x*L+s[i].y/L);

			if(R<=r)ans=min(ans,s[i].x+s[i].y+s[i].x*R+s[i].y/R);

		}

		else ans=min(ans,s[i].x+s[i].y+s[i].x*z+s[i].y/z);

	}

	printf("%.4lf\n",ans);

	return 0;

}

巴特西

P3291-[SCOI2016]妖怪【凸壳】

正题

题目大意

解题思路

code

最新文章

热门文章