XJOI网上同步测试DAY14 T2-LMLPHP

XJOI网上同步测试DAY14 T2-LMLPHP

思路:先考虑在D高度的最小圆覆盖,再一层一层往下走时,可以保证圆心与最开始的圆相同的时候答案是最优的。

时间复杂度O(n)

有一个坑点,就是我用了srand(time(NULL))就T了,RP太差了。。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<time.h>
const double eps=1e-;
const double inf=1e60;
const double Pi=acos(-);
struct Point{
double x,y;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
}p[],O;
struct Line{
Point s,e;
Line(){}
Line(Point s0,Point e0):s(s0),e(e0){}
};
Point operator -(Point p1,Point p2){
return Point(p1.x-p2.x,p1.y-p2.y);
}
Point operator +(Point p1,Point p2){
return Point(p1.x+p2.x,p1.y+p2.y);
}
Point operator *(Point p,double x){
return Point(p.x*x,p.y*x);
}
Point operator /(Point p,double x){
return Point(p.x/x,p.y/x);
}
double operator *(Point p1,Point p2){
return p1.x*p2.y-p1.y*p2.x;
}
double sqr(double x){
return x*x;
}
double dis(Point p1){
return sqrt(sqr(p1.x)+sqr(p1.y));
}
double dis(Point p1,Point p2){
return dis(p1-p2);
}
int n;
double cost[],D,R;
int H;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
Point inter(Line p1,Line p2){
double k1=(p2.e-p1.s)*(p1.e-p1.s);
double k2=(p1.e-p1.s)*(p2.s-p1.s);
double t=(k2)/(k1+k2);
double x=p2.s.x+(p2.e.x-p2.s.x)*t;
double y=p2.s.y+(p2.e.y-p2.s.y)*t;
return Point(x,y);
}
Point turn(Point p,double ang){
double Cos=cos(ang);
double Sin=sin(ang);
double x=Cos*p.x-Sin*p.y;
double y=Cos*p.y+Sin*p.x;
return Point(x,y);
}
Point calc(Point p1,Point p2,Point p3){
Point a=(p1+p2)/2.0;
Point b=(p2+p3)/2.0;
Point A=turn(p2-p1,Pi/2.0)+a;
Point B=turn(p3-p2,Pi/2.0)+b;
return inter(Line(a,A),Line(b,B));
}
int main(){
//srand(time(NULL));
int DD;
n=read();H=read();scanf("%lf",&R);DD=read();
D=DD;
for (int i=;i<=H;i++) cost[i]=read();
for (int i=;i<=n;i++) p[i].x=read(),p[i].y=read();
for (int i=;i<=n;i++)
std::swap(p[rand()%n+],p[rand()%n+]);
O=p[];double r=;
for (int i=;i<=n;i++)
if (dis(O,p[i])>r+eps){
O=p[i];r=;
for (int j=;j<i;j++)
if (dis(O,p[j])>r+eps){
O=(p[i]+p[j])/2.0;
r=dis(O,p[j]);
for (int k=;k<j;k++)
if (dis(O,p[k])>r+eps){
O=calc(p[i],p[j],p[k]);
r=dis(O,p[k]);
}
}
}
double ans=inf,rr,xx,yy;
int hh;
H=std::min(H,DD);
for (int i=;i<=H;i++){
double sxr=std::max(R,r-sqrt(sqr(D)-sqr((double)i)));
if (sxr*cost[i]<ans){
ans=sxr*cost[i];
rr=sxr;
xx=O.x;
yy=O.y;
hh=i;
}
}
printf("%.10f\n",ans);
printf("%.10f %.10f %d %.10f\n",xx,yy,hh,rr);
}
05-06 04:22