Description：

给一个平面和平面上的 $n$ 个点，要求选一个高度 $h$ 画一个圆，代价为 $r\times val_h$ ，要求半径大于等于 $R$ ，并且平面上所有点到圆上最近一点的三维距离不超过 $D$ 。

$1\leqslant N,H\leqslant 500000$

Solution：

先列答案的式子： $$ \begin{align} ans&=\min_{h=0}^H\Biggl(\max\Bigl(R,\min_{x,y}\max_{k=1}^n(\sqrt{(x-x_k)^2+(y-y_k)^2+h^2}-\sqrt{D^2-h^2})\Bigr)\times val[h]\Biggr)\\ ans&=\min_{h=0}^H\Biggl(\max\Bigl(R,\min_{x,y}\max_{k=1}^n(\sqrt{(x-x_k)^2+(y-y_k)^2+h^2})-\sqrt{D^2-h^2}\Bigr)\times val[h]\Biggr)\\ ans&=\min_{h=0}^H\Biggl(\max\Bigl(R,\sqrt{\min_{x,y}\max_{k=1}^n\bigl((x-x_k)^2+(y-y_k)^2\bigr)+h^2}-\sqrt{D^2-h^2}\Bigr)\times val[h]\Biggr) \end{align} $$ 设： $$ v=\min_{x,y}\max_{k=1}^n\bigl((x-x_k)^2+(y-y_k)^2\bigr) $$ 可以发现 $v$ 求的其实就是最小圆覆盖，于是式子变成了： $$ ans=\min_{h=0}^H\Biggl(\max\Bigl(R,\sqrt{v+h^2}-\sqrt{D^2-h^2}\Bigr)\times val[h]\Biggr) $$ 这个式子显然暴力计算就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,h,r,d;

#define MAXN 500010

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int val[MAXN];

struct point

{

	double x,y;

}p[MAXN];

point o;

double l;

const double eps = 1e-8;

bool equ(double a,double b){return fabs(a - b) <= eps;}

double dis(point a,point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}

void get(point a,point b)

{

	o.x = (a.x + b.x) / 2;o.y = (a.y + b.y) / 2;l = dis(a,o);

	return;

}

void get(point a,point b,point c)

{

	double k1 = -(b.x - a.x) / (b.y - a.y),x1 = (b.x + a.x) / 2,y1 = (b.y + a.y) / 2,b1 = y1 - k1 * x1;

	double k2 = -(c.x - b.x) / (c.y - b.y),x2 = (c.x + b.x) / 2,y2 = (c.y + b.y) / 2,b2 = y2 - k2 * x2;

	double k3 = -(c.x - a.x) / (c.y - a.y),x3 = (c.x + a.x) / 2,y3 = (c.y + a.y) / 2,b3 = y3 - k3 * x3;

	if(equ(k1,k2) && equ(k2,k3))

	{

		int d1 = dis(a,b),d2 = dis(a,c),d3 = dis(b,c);

		if(d1 >= max(d2,d3)){get(a,b);return;}

		if(d2 >= max(d1,d3)){get(a,c);return;}

		if(d3 >= max(d1,d2)){get(b,c);return;}

	}

	if(!equ(k1,k2))o.y = (b2 * k1 - b1 * k2) / (k1 - k2),o.x = (o.y - b1) / k1,l = dis(o,a);

	else if(!equ(k2,k3))o.y = (b2 * k3 - b3 * k2) / (k3 - k2),o.x = (o.y - b3) / k3,l = dis(o,a);

	else o.y = (b3 * k1 - b1 * k3) / (k1 - k3),o.x = (o.y - b1) / k1,l = dis(o,a);

	return;

}

bool in(point p)

{

	return dis(o,p) <= l;

}

int main()

{

	scanf("%d%d%d%d",&n,&h,&r,&d);

	for(int i = 0;i <= h;++i)val[i] = rd();

	for(int i = 1;i <= n;++i)p[i].x = rd(),p[i].y = rd();

	random_shuffle(p + 1,p + 1 + n);

	o = p[1];l = 0;

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

	{

		if(in(p[i]))continue;

		get(p[1],p[i]);

		for(int j = 2;j < i;++j)

		{

			if(in(p[j]))continue;

			get(p[i],p[j]);

			for(int k = 1;k < j;++k)

			{

				if(in(p[k]))continue;

				get(p[i],p[j],p[k]);

			}

		}

	}

	double v = 0;

	for(int i = 1;i <= n;++i)v = max(v,dis(o,p[i]));

	double ans = 10000000000000000000,ansr;

	int ansh;

	for(int i = 0;i <= min(h,d);++i)

	{

		double rr = max(1.0 * r,v - sqrt(d * d - i * i));

		if(rr * val[i] < ans)ans = rr * val[i],ansr = rr,ansh = i;

	}

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

	printf("%.9lf %.9lf %d %.9lf\n",o.x,o.y,ansh,ansr);

	return 0;

}