Description：

给出 $a,b,d_i,s_i$ ，要求： $$ \sum_{i=1}^nd_i(\max(0,ax_i+bs_i))\leqslant E $$ 最大化： $$ f(x_1,x_2,\dots,x_n)=\sum_{i=1}^n\frac{d_i}{x_i} $$ 要求 $v\leqslant maxv$

$1\leqslant t\leqslant 100,1\leqslant n\leqslant 10^4$

Solution：

首先 $ax_i+bs_i\geqslant 0$ 一定比 $<0$ 更优，所以那个大于号其实没用，根据骑行川藏的经验我们可以套用拉格朗日乘数法： $$ L(x_1,x_2,\dots,x_n)=\sum_{i=1}^n\frac{d_i}{x_i}+\lambda(\sum_{i=1}^n(d_iax_i+d_ibs_i)-E) $$ 求偏导得： $$ L'(x_i)=-d_ix_i^{-2}+\lambda d_ia=0\\ \lambda ax_i^2=1 $$ 我们发现所有的 $x_i$ 都应该是一样的。 于是二分 $x_i$ ，然后判断 $\varphi$ 的值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

double a,b,vmax,E;

int n;

#define MAXN 10010

double d[MAXN],s[MAXN];

double calc(double v)

{

	double sum = 0;

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

	{

		sum += max(0.0,d[i] * (a * v + b * s[i]));

	}

	return sum;

}

#define eps 1e-12

void work()

{

	scanf("%lf%lf%lf%lf",&a,&b,&vmax,&E);

	scanf("%d",&n);

	double x,y;

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

	{

		scanf("%lf%lf",&x,&y);

		x /= 1000;y /= 1000;

		d[i] = sqrt(x * x + y * y);

		s[i] = y / x;

	}

	double l = 0,r = vmax,mid;

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

	{

		mid = (l + r) / 2;

		if(calc(mid) <= E)l = mid;

		else r = mid;

	}

	double ans = 0.0;

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

	{

		double o = a * l + b * s[i];

		double v = l;

		if(o <= eps)

		{

			v = min(-b * s[i] / a,vmax);

		}

		if(v <= eps)

		{

			puts("IMPOSSIBLE");

			return;

		}

		ans += d[i] / v;

	}

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

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}