网站域名注册服务商,重庆个人网络营销电话,易捷网站内容管理系统漏洞,电商平台运营正题
题目链接:https://www.luogu.com.cn/problem/P3291 题目大意
给出 nnn 个数字对 (atk,dnf)(atk,dnf)(atk,dnf)#xff0c;求一个(a,b)(a,b)(a,b)。
对于每个数字对可以选择任意一个实数kkk让其变为(atkka,dnf−ka)(atkk\times a,dnf-k\times a)(atkka,dnf−ka)#x…正题
题目链接:https://www.luogu.com.cn/problem/P3291 题目大意
给出 nnn 个数字对 (atk,dnf)(atk,dnf)(atk,dnf)求一个(a,b)(a,b)(a,b)。
对于每个数字对可以选择任意一个实数kkk让其变为(atkk×a,dnf−k×a)(atkk\times a,dnf-k\times a)(atkk×a,dnf−k×a)但是操作完之后两个数字都非负。记atk/dnf(a,b)atk/dnf(a,b)atk/dnf(a,b)表示在(a,b)(a,b)(a,b)下atk/dnfatk/dnfatk/dnf的最大值。
然后要求最小化max{atki(a,b),dnfi(a,b)}max\{atk_i(a,b),dnf_i(a,b)\}max{atki(a,b),dnfi(a,b)}。
1≤n≤106,1≤atk,dnf≤1081\leq n\leq 10^6,1\leq atk,dnf\leq 10^81≤n≤106,1≤atk,dnf≤108 解题思路
首先视(atk,dnf)(atk,dnf)(atk,dnf)为一个点的话那么对于任意一个(a,b)(a,b)(a,b)答案肯定是在上凸壳上的。
然后考虑实际上我们并不需要用到(a,b)(a,b)(a,b)只需考虑ba\frac{b}{a}ab的值定义kbak\frac{b}{a}kab
然后就是要求最小化用aia_iai代atkiatk_iatkidid_idi代dnfidnf_idnfi aibiaikbi1ka_ib_ia_ikb_i\frac{1}{k}aibiaikbik1 考虑这个点在kkk的哪些区间由它取到最大值对于一个jjj需要满足 aibiaikbi1kajbjajkbj1ka_ib_ia_ikb_i\frac{1}{k}a_jb_ja_jkb_j\frac{1}{k}aibiaikbik1ajbjajkbjk1 化一下 (ai−aj)k2(ai−ajbi−bj)k(bi−bj)0(a_i-a_j)k^2(a_i-a_jb_i-b_j)k(b_i-b_j)0(ai−aj)k2(ai−ajbi−bj)k(bi−bj)0 然后就是一个二次不等式并且考虑到jjj只需考虑凸壳上iii左右连接的两个点解出来我们可以得到kkk的合法范围。
然后上面那个是一个对钩函数现在只需在这个范围内求这个对钩函数的最小值就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N1e610;
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 db*b-4.0*a*c;if(d0)return 0;dsqrt(d);double x0(-b-d)/(2*a),x1(-bd)/(2*a);if(x0x1)swap(x0,x1);lx0;rx1;return 1;
}
bool cmp(node x,node y)
{return (x.xy.x)?(x.yy.y):(x.xy.x);}
double solpe(node x,node y)
{return (y.y-x.y)/(y.x-x.x);}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%lf%lf,p[i].x,p[i].y);sort(p1,p1n,cmp);for(int i1;in;i){while(top1solpe(s[top-1],s[top])solpe(s[top-1],p[i]))top--;s[top]p[i];}ans1e18;for(int i1;itop;i){double zsqrt(s[i].y/s[i].x);double l0,r1e18,L1,R1;bool flag1;if(i1)calc(s[i].x-s[i-1].x,s[i].x-s[i-1].xs[i].y-s[i-1].y,s[i].y-s[i-1].y,L,R);if(itop)flagcalc(s[i].x-s[i1].x,s[i].x-s[i1].xs[i].y-s[i1].y,s[i].y-s[i1].y,l,r);if(!flag)continue;if(Ll)lmax(R,l);if(Rr)rmin(r,L);if(lr||r0)continue;zmax(z,l);zmin(z,r);if(zLzR){if(Ll)ansmin(ans,s[i].xs[i].ys[i].x*Ls[i].y/L);if(Rr)ansmin(ans,s[i].xs[i].ys[i].x*Rs[i].y/R);}else ansmin(ans,s[i].xs[i].ys[i].x*zs[i].y/z);}printf(%.4lf\n,ans);return 0;
}
