NC243749. Known as the Fruit Brother
描述
输入描述
见 PDF 题面
输出描述
见 PDF 题面
示例1
输入:
1 2 2 0 2 7 4 -3 3 8 2 1 1 6 6
输出:
9.543203767
C++(clang++ 11.0.1) 解法, 执行用时: 607ms, 内存消耗: 58680K, 提交时间: 2022-10-02 00:04:32
#include<bits/stdc++.h>
#define int long long
#define MAXN 600001
using namespace std;
int n,m,xs,ys,xt,yt,bia;
double R;
const double eps = 1e-8;
const double pi = acos(-1.0);
int sgn(double x)
{
if(fabs(x) < eps) return 0;//认为是0
if(x < 0) return -1;//负数
else return 1;//正数
}
inline double sqr(double x){return x*x;}
struct Point
{
double x,y;
Point(){}
Point(double X,double Y){x=X;y=Y;}
void input(){scanf("%lf%lf",&x,&y);}
void output(){printf("%.2f%.2f",x,y);}
bool operator==(Point b) const//判断是否相等
{return sgn(x-b.x)==0&&sgn(y-b.y)==0;}
bool operator<(Point b) const
{return sgn(x-b.x)==0? sgn(y-b.y)<0:x<b.x;}
Point operator+(const Point &b) const
{return Point(x+b.x,y+b.y);}//加
Point operator-(const Point &b) const
{return Point(x-b.x,y-b.y);}//减
Point operator*(const double &k) const
{return Point(x*k,y*k);}//乘
Point operator/(const double &k) const
{return Point(x/k,y/k);}//除
double operator^(const Point &b) const
{return x*b.y-y*b.x;}//叉积
double operator*(const Point &b) const
{return x*b.x+y*b.y;}//点积
double lenth(){return hypot(x,y);}//返回长度
double lenth2(){return x*x+y*y;}//返回长度的平方
double distance(Point p){return hypot(x-p.x,y-p.y);}//两点长度
Point trunc(double r)//向量长度变为r
{
double l=lenth();
if(!sgn(l)) return *this;
r/=l;
return Point(x*r,y*r);
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point S,Point E){s=S;e=E;}
bool operator==(Line v){return (s==v.s)&&(e==v.e);}
void adjust(){if(e<s)swap(s,e);}
double length(){return s.distance(e);}//线段长度
Point crosspoint(Line v)
{//求两直线的交点
double a1=(v.e-v.s)^(s-v.s);
double a2=(v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
int relation(Point p)//点线关系
{//1左侧 2右侧 3线上
int c=sgn((p-s)^(e-s));
if(c<0) return 1;
else if(c>0) return 2;
else return 3;
}
bool parallel(Line v)
{//判断两向量平行(对应直线平行或重合)
return sgn((e-s)^(v.e-v.s))==0;
}
int linecrossline(Line v)//两直线关系
{//0平行 1重合 2相交
if((*this).parallel(v)) return v.relation(s)==3;
return 2;
}
bool ifcrossline(Line v)
{//判断两线段是否相交
if(!(max(s.x,e.x)+eps>=min(v.s.x,v.e.x)&&min(s.x,e.x)<=max(v.s.x,v.e.x)+eps))
return 0;
if(!(max(s.y,e.y)+eps>=min(v.s.y,v.e.y)&&min(s.y,e.y)<=max(v.s.y,v.e.y)+eps))
return 0;
if(((e-s)^(v.s-s))*((e-s)^(v.e-s))>eps)
return 0;
if(((v.e-v.s)^(s-v.s))*((v.e-v.s)^(e-v.s))>eps)
return 0;
return 1;
}
double dispointtoline(Point p)
{//点到直线的距离
return fabs((p-s)^(e-s))/length();
}
double dispointtoseg(Point p)
{//点到线段的距离
if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0)
return min(p.distance(s),p.distance(e));
return dispointtoline(p);
}
Point lineprog(Point p)
{//返回点p在直线上的投影
return s+(((e-s)*((e-s)*(p-s)))/((e-s).lenth2()));
}
};
struct Circle
{
Point p;//圆心
double r;//半径
Circle(){}
Circle(Point P,double R){p=P;r=R;}
Circle(double x,double y,double R){p=Point(x,y);r=R;}
void input(){p.input();scanf("%lf",&r);}
void output(){printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);}
bool operator==(Circle v)
{return (p==v.p)&&sgn(r-v.r)==0;}
bool operator<(Circle v) const
{return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));}
double area(){return pi*r*r;}//面积
double circumference(){return 2*pi*r;}//周长
int relation(Point b)//点和圆的关系
{//0圆外 1圆上 2圆内
double dst=b.distance(p);
if(sgn(dst-r)<0) return 2;
else if(sgn(dst-r)==0) return 1;
return 0;
}
int relationseg(Line v)//线段和圆的关系
{//0圆外 1相切 2圆内
double dst=v.dispointtoseg(p);
if(sgn(dst-r)<0) return 2;
else if(sgn(dst-r)==0) return 1;
return 0;
}
int relationline(Line v)//直线和圆的关系
{//0圆外 1相切 2圆内
double dst=v.dispointtoline(p);
if(sgn(dst-r)<0) return 2;
else if(sgn(dst-r)==0) return 1;
return 0;
}
int pointcrossline(Line v,Point &p1,Point &p2)
{//求直线和圆的交点个数
if(!(*this).relationline(v)) return 0;
Point a=v.lineprog(p);
double d=v.dispointtoline(p);
d=sqrt(r*r-d*d);
if(sgn(d)==0){p1=a;p2=a;return 1;}
p1=a+(v.e-v.s).trunc(d);
p2=a-(v.e-v.s).trunc(d);
return 2;
}
};
struct squ
{
Point leftdown;
Point leftup;
Point rightup;
Point rightdown;
}a[MAXN];
Point c[MAXN],s,t,sp[MAXN*10];
Line l[MAXN*10];
int head[MAXN*10],cnt,vis[MAXN*10],fa[MAXN*10];
double dis[MAXN];
struct node
{
int nxt,to;
double cost;
}e[MAXN*10];
bool check(Point x)
{
int flag=1;
for(int i=1;i<=n;i++)
{
if(a[i].leftup.x<=x.x&&a[i].leftup.y>=x.y)
if(a[i].rightup.x>=x.x&&a[i].rightup.y>=x.y)
if(a[i].rightdown.x>=x.x&&a[i].rightdown.y<=x.y)
if(a[i].leftdown.x<=x.x&&a[i].leftdown.y<=x.y)
{
flag=0;
break;
}
}
return flag;
}
void insert(int now,int aim,double wealth)
{
//cout<<"insert:from"<<now<<" to "<<aim<<" cost:"<<wealth<<endl;
e[++cnt].nxt=head[now];
e[cnt].to=aim;
e[cnt].cost=wealth;
head[now]=cnt;
}
void dijkstra()
{
priority_queue<pair<double,int> >q;
for(int i=1;i<MAXN;i++) dis[i]=1e18;
memset(vis,0,sizeof(vis));
dis[0]=0;
q.push(make_pair(0,0));
while(!q.empty())
{
int u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int temp=e[i].to;
if(dis[temp]>dis[u]+e[i].cost)
{
dis[temp]=dis[u]+e[i].cost;
q.push(make_pair(-dis[temp],temp));
}
}
}
}
Point poly[MAXN];
signed main()
{
scanf("%lld%lld%lf",&n,&m,&R);
for(int i=1;i<=n;i++)
{
a[i].leftdown.input();
a[i].rightup.input();
a[i].leftup.x=a[i].leftdown.x;
a[i].leftup.y=a[i].rightup.y;
a[i].rightdown.x=a[i].rightup.x;
a[i].rightdown.y=a[i].leftdown.y;
l[(i-1)*4+1]=Line(a[i].leftdown,a[i].leftup);
l[(i-1)*4+2]=Line(a[i].leftup,a[i].rightup);
l[(i-1)*4+3]=Line(a[i].rightup,a[i].rightdown);
l[(i-1)*4+4]=Line(a[i].rightdown,a[i].leftdown);
poly[(i-1)*4+1]=a[i].leftup;
poly[(i-1)*4+2]=a[i].rightup;
poly[(i-1)*4+3]=a[i].rightdown;
poly[(i-1)*4+4]=a[i].leftdown;
}
for(int i=1;i<=m;i++)
{
c[i].input();
}
s.input();t.input();
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)//圆圆相连
{
if(i!=j)
{
double dis=c[i].distance(c[j]);
if(dis<=R)
{
insert(n*4+i,n*4+j,0);
continue;
}
Circle cir=Circle(c[i],R);
Line temp=Line(c[i],c[j]);
Point kkk1,kkk2;
int pot=cir.pointcrossline(temp,kkk1,kkk2);
if(temp.dispointtoseg(kkk1)>eps) kkk1=kkk2;
temp=Line(kkk1,c[j]);
if(!check(kkk1)) continue;
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(n*4+i,n*4+j,dis-R);
}
}
for(int j=1;j<=4*n;j++)//圆矩相连
{
double dis=c[i].distance(poly[j]);
if(dis<=R)
{
insert(n*4+i,j,0);
continue;
}
Circle cir=Circle(c[i],R);
Line temp=Line(c[i],poly[j]);
Point kkk1,kkk2;
int pot=cir.pointcrossline(temp,kkk1,kkk2);
if(temp.dispointtoseg(kkk1)>eps) kkk1=kkk2;
temp=Line(kkk1,poly[j]);
if(!check(kkk1)) continue;
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(n*4+i,j,dis-R);
}
}
for(int i=1;i<=n;i++)//矩形自连
{
insert((i-1)*4+1,(i-1)*4+2,a[i].leftup.distance(a[i].rightup));
insert((i-1)*4+2,(i-1)*4+1,a[i].leftup.distance(a[i].rightup));
insert((i-1)*4+2,(i-1)*4+3,a[i].rightup.distance(a[i].rightdown));
insert((i-1)*4+3,(i-1)*4+2,a[i].rightup.distance(a[i].rightdown));
insert((i-1)*4+3,(i-1)*4+4,a[i].rightdown.distance(a[i].leftdown));
insert((i-1)*4+4,(i-1)*4+3,a[i].rightdown.distance(a[i].leftdown));
insert((i-1)*4+4,(i-1)*4+1,a[i].leftdown.distance(a[i].leftup));
insert((i-1)*4+1,(i-1)*4+4,a[i].leftdown.distance(a[i].leftup));
}
for(int i=1;i<=4*n;i++)
{
for(int j=1;j<=4*n;j++)//矩矩相连
{
if(i==j) continue;
int test1=i/4+(i%4==0? 0:1);
int test2=j/4+(j%4==0? 0:1);
if(test1==test2) continue;
Line temp=Line(poly[i],poly[j]);
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(i,j,poly[i].distance(poly[j]));
}
}
for(int i=1;i<=4*n;i++)//矩形连圆
{
for(int j=1;j<=m;j++)
{
Line temp=Line(poly[i],c[j]);
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(i,n*4+j,poly[i].distance(c[j]));
}
}
for(int i=1;i<=4*n;i++)
{
Line temp=Line(s,poly[i]);
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(0,i,s.distance(poly[i]));
temp=Line(t,poly[i]);
flag=1;
group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(i,n*4+m+1,t.distance(poly[i]));
}
for(int i=1;i<=m;i++)
{
Line temp=Line(s,c[i]);
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(0,n*4+i,s.distance(c[i]));
}
for(int i=1;i<=m;i++)
{
double dis=t.distance(c[i]);
if(dis<=R)
{
insert(4*n+i,4*n+m+1,0);
continue;
}
Circle cir=Circle(c[i],R);
Line temp=Line(c[i],t);
Point kkk1,kkk2;
int pot=cir.pointcrossline(temp,kkk1,kkk2);
if(temp.dispointtoseg(kkk1)>eps) kkk1=kkk2;
temp=Line(kkk1,t);
if(!check(kkk1)) continue;
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(4*n+i,4*n+m+1,dis-R);
}
Line temp=Line(s,t);
int flag=1;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=0;
break;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag=0;
break;
}
}
if(flag) insert(0,4*n+m+1,s.distance(t));
for(int i=1;i<=m;i++)
{
Circle temp=Circle(c[i],R);
for(int k=1;k<=4*n;k++)
{
Point kkk1,kkk2;
int pot=temp.pointcrossline(l[k],kkk1,kkk2);
if(pot==0) continue;
else
{
if(l[k].dispointtoseg(kkk1)<=eps)
{
bia++;
int rod=k/4+(k%4==0? 0:1);
fa[bia]=rod;
sp[bia]=kkk1;
insert(4*n+i,4*n+m+1+bia,0);
insert(4*n+m+1+bia,k,kkk1.distance(poly[k]));
insert(4*n+m+1+bia,k-1+((k-1)%4==0? 4:0),kkk1.distance(poly[k-1+((k-1)%4==0? 4:0)]));
}
if(l[k].dispointtoseg(kkk2)<=eps)
{
bia++;
int rod=k/4+(k%4==0? 0:1);
fa[bia]=rod;
sp[bia]=kkk2;
insert(4*n+i,4*n+m+1+bia,0);
insert(4*n+m+1+bia,k,kkk2.distance(poly[k]));
insert(4*n+m+1+bia,k-1+((k-1)%4==0? 4:0),kkk2.distance(poly[k-1+((k-1)%4==0? 4:0)]));
}
}
}
}
for(int i=1;i<=bia;i++)
{
for(int j=1;j<=m;j++)
{
Line temp=Line(sp[i],c[j]);
int flag=0;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=2;
break;
}
if(k/4+(k%4==0? 0:1)==fa[i])
{
flag++;
continue;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag++;
}
}
if(flag<=1) insert(4*n+m+1+i,n*4+j,sp[i].distance(c[j]));
}
for(int j=1;j<=4*n;j++)
{
Line temp=Line(sp[i],poly[j]);
int flag=0;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=2;
break;
}
if(k/4+(k%4==0? 0:1)==fa[i])
{
flag++;
continue;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag++;
}
}
if(flag<=1) insert(4*n+m+1+i,j,sp[i].distance(poly[j]));
}
Line temp=Line(sp[i],t);
int flag=0;
int group=0;
for(int k=1;k<=4*n;k++)
{
if(k%4==1) group=0;
int rel=temp.ifcrossline(l[k]);
if(rel==1)
{
group++;
if(group==4)
{
flag=2;
break;
}
if(k/4+(k%4==0? 0:1)==fa[i])
{
flag++;
continue;
}
Point kkk=temp.crosspoint(l[k]);
if(kkk==l[k].e||kkk==l[k].s) continue;
if(temp.linecrossline(l[k])==1) continue;
flag++;
}
}
if(flag<=1) insert(4*n+m+1+i,4*n+m+1,sp[i].distance(t));
}
dijkstra();
printf("%.9lf\n",dis[4*n+m+1]);
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 2855ms, 内存消耗: 14716K, 提交时间: 2022-09-24 20:13:43
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
const ldb eps = 1e-14;
int sgn(ldb x){
if(x > eps) return 1;
if(x < -eps) return -1;
return 0;
}
struct point{
ldb x,y;
point() : x(), y() {}
point(ldb _x,ldb _y) : x(_x), y(_y) {}
};
point operator + (point x,point y){
x.x += y.x; x.y += y.y;
return x;
}
point operator - (point x,point y){
x.x -= y.x; x.y -= y.y;
return x;
}
point operator * (ldb x,point y){
y.x *= x; y.y *= x;
return y;
}
bool operator == (point p1,point p2){
return sgn(p1.x - p2.x) == 0 && sgn(p1.y - p2.y) == 0;
}
struct line{
point a,b;
line() : a(), b() {}
line(point _a,point _b) : a(_a), b(_b) {}
};
ldb dist(point p1,point p2){
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
ldb len(point p1){
return sqrt(p1.x * p1.x + p1.y * p1.y);
}
ldb det(point p1,point p2){
return p1.x * p2.y - p1.y * p2.x;
}
ldb dot(point p1,point p2){
return p1.x * p2.x + p1.y * p2.y;
}
bool intersec(line x,line y){
return sgn(det(x.a - y.a,y.b - y.a) * det(x.b - y.a,y.b - y.a)) <= 0;
}
bool exclusion_test(line x,line y){
return sgn(min(x.a.x,x.b.x) - max(y.a.x,y.b.x)) <= 0 && sgn(min(y.a.x,y.b.x) - max(x.a.x,x.b.x)) <= 0 && sgn(min(x.a.y,x.b.y) - max(y.a.y,y.b.y)) <= 0 && sgn(min(y.a.y,y.b.y) - max(x.a.y,x.b.y)) <= 0;
}
bool seg_intersec(line x,line y){
return exclusion_test(x,y) && intersec(x,y) && intersec(y,x);
}
bool point_on_seg(point x,line y){
return sgn(dot(y.a - x,y.b - x)) <= 0 && sgn(det(y.a - x,y.b - x)) == 0;
}
ldb distp(point x,line y){
return fabs(det(y.a - x,y.b - x)) / len(y.b - y.a);
}
point project_point(point x,line y){
point v = y.b - y.a;
return y.a + (dot(v,x - y.a) / dot(v,v)) * v;
}
int n,m,R;
line ob[305];
point s[30005]; int sc = 0,obc = 0;
struct node{
int x; ldb dis;
node(int _x = 0,ldb _dis = 0.0) : x(_x), dis(_dis) {}
bool operator < (const node &nd)const{
return nd.dis < dis;
}
};
priority_queue <node> pq;
int ec = 0,to[30000005],nxt[30000005],hed[30005];
ldb w[30000005];
void add_edge(int f,int t,ldb cst){
++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec; w[ec] = cst;
}
ldb dis[30005]; int vis[30005];
void dijkstra(int s){
for(int i = 1;i <= sc;i ++) dis[i] = 1e18;
pq.push(node(s,0.0));
dis[s] = 0.0; vis[s] = 0;
while(!pq.empty()){
node h = pq.top(); pq.pop();
int u = h.x;
if(vis[u]) continue;
vis[u] = 1;
for(int v,i = hed[u];i;i = nxt[i]){
v = to[i];
if(dis[v] > dis[u] + w[i]){
dis[v] = dis[u] + w[i];
pq.push(node(v,dis[v]));
}
}
}
}
int type2,type3;
bool judge(point x,point y){
for(int k = 2;k + 4 < type2;k += 4){
if(!point_on_seg(s[k + 1],line(x,y)) && !point_on_seg(s[k + 3],line(x,y)) && seg_intersec(line(s[k + 1],s[k + 3]),line(x,y))) return 1;
if(!point_on_seg(s[k + 2],line(x,y)) && !point_on_seg(s[k + 4],line(x,y)) && seg_intersec(line(s[k + 2],s[k + 4]),line(x,y))) return 1;
}
return 0;
}
bool judge2(point x){
for(int k = 2;k + 4 < type2;k += 4){
ldb xl = s[k + 1].x,yl = s[k + 1].y,xr = s[k + 3].x,yr = s[k + 3].y;
if(xl + eps < x.x && x.x + eps < xr && yl + eps < x.y && x.y + eps < yr) return 1;
}
return 0;
}
point lcsec[3];
int sec_line_circle(line x,ldb cx,ldb cy,ldb cr,point *ret){
ldb dis = distp(point(cx,cy),x);
if(sgn(dis - cr) > 0) return 0;
point proj = project_point(point(cx,cy),x);
if(sgn(dis - cr) == 0){
ret[0] = proj;
return 1;
}
point v = x.b - x.a; ldb dv = sqrt(cr * cr - dis * dis);
ret[0] = proj + (dv / len(v)) * v;
ret[1] = proj - (dv / len(v)) * v;
return 2;
}
int main(){
ios::sync_with_stdio(false);
// S = 1, T = 2
sc = 2;
cin >> n >> m >> R;
for(int xl,yl,xr,yr,i = 1;i <= n;i ++){
cin >> xl >> yl >> xr >> yr;
s[++ sc] = point(xl,yl);
s[++ sc] = point(xl,yr);
s[++ sc] = point(xr,yr);
s[++ sc] = point(xr,yl);
ob[++ obc] = line(point(xl,yl),point(xl,yr));
ob[++ obc] = line(point(xl,yr),point(xr,yr));
ob[++ obc] = line(point(xr,yr),point(xr,yl));
ob[++ obc] = line(point(xr,yl),point(xl,yl));
}
type2 = sc + 1;
for(int x,y,i = 1;i <= m;i ++){
cin >> x >> y;
s[++ sc] = point(x,y);
}
type3 = sc + 1;
for(int i = type2;i < type3;i ++){
for(int j = 1;j <= obc;j ++){
int cnt = sec_line_circle(ob[j],s[i].x,s[i].y,R,lcsec);
//cout << "CIRC: " << i << ' ' << j << ' ' << cnt << endl;
for(int k = 0;k < cnt;k ++){
//cout << s[i].x << ',' << s[i].y << ' ' << lcsec[k].x << ',' << lcsec[k].y << ' ' << dist(s[i],lcsec[k]) << endl;
if(point_on_seg(lcsec[k],line(ob[j]))) s[++ sc] = lcsec[k];
}
}
}
cin >> s[1].x >> s[1].y >> s[2].x >> s[2].y;
//cout << type3 << ' ' << sc << endl;
for(int i = 1;i <= sc;i ++){
//cout << i << ' ' << s[i].x << ' ' << s[i].y << '\n';
for(int j = 1;j <= sc;j ++){
if(s[i] == s[j]) continue;
if(i >= type3 && j >= type3) break;
ldb dis = dist(s[i],s[j]);
point tmp = s[i];
if(i >= type2 && i < type3){
dis = max((ldb)(0.0),dis - R);
if(dis <= eps){
add_edge(i,j,dis);
continue;
}
s[i] = s[i] + (1.0 * R / len(s[j] - s[i])) * (s[j] - s[i]);
if(judge2(s[i])) dis = 1e18;
}
if(judge(s[i],s[j])) dis = 1e18;
s[i] = tmp;
//cout << i << ',' << j << ',' << dis << endl;
if(dis < 1e17) add_edge(i,j,dis);
}
}
dijkstra(1);
cout << fixed << setprecision(14) << dis[2] << '\n';
return 0;
}