大佬教程收集整理的这篇文章主要介绍了P3291-[SCOI2016]妖怪【凸壳】，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

正题

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

---

题目大意

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

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

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

(1leq nleq 10^6,1leq atk,dnfleq 10^8)

---

解题思路

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

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

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

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

化一下

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

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

时间复杂度(O(nlog 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("%.4lfn",ans);
	return 0;
}

大佬总结

以上是大佬教程为你收集整理的P3291-[SCOI2016]妖怪【凸壳】全部内容，希望文章能够帮你解决P3291-[SCOI2016]妖怪【凸壳】所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。