88 条题解
-
3
PowderHan LV 10 @ 2017-05-07 12:47:15
/*
嗯一道计算几何+最短路
黑书上计算几何有这道题目
其实题目不难的
唯一的难度就是判断两点能否直接到达
即两点连线上是否有别的墙挡住
这个据说是可以用叉积很快的
但是如果用相似三角形比例
也是可以写出来的
然后我们对于每堵墙两个洞即四个点
我们可以判断能否在一条直线上中间无障碍物
如果可以就是他们的欧几里得距离
如果不可以就设为INF
建立邻接矩阵
然后随便跑个最短路就好了
还是FLoyd最方便最快捷
Orz主要还是最好写2333333333
然后判断是否能连线
我这种弱弱真的懒得写啊
就随便复制了个叉积的然后改了一下用进来了
千万别学我Orz
嗯就这样水过去吧
*/#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=100; const double INF=999.0; struct node { double x,y; }p[MAXN]; int n,K; double d[MAXN][MAXN]; double inline ojld(int i,int j) { return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) +(p[i].y-p[j].y)*(p[i].y-p[j].y)); } double det(double x1,double y1,double x2,double y2)//行列式 { return x1*y2-x2*y1; } double cross(node p0,node p1,node p2)//叉积 { double ans = det(p1.x-p0.x,p1.y-p0.y,p2.x-p0.x,p2.y-p0.y); return ans; } bool check(int a,int b)//判断能否连通 { if(p[a].x == p[b].x) return false; for(int i = a+1;i < b;i++) { if(p[i].x == p[a].x || p[i].x == p[b].x) continue; node temp; if(i%4==1) { temp.x = p[i].x,temp.y = 10; if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0) return false; } if(i%4==0) { temp.x = p[i].x,temp.y = 0; if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0) return false; } if(i%4==2) { temp.x = p[i+1].x,temp.y = p[i+1].y; if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0) return false; } } return true; } void init() { double x; cin>>n; K=4*n+1; for(int i=0;i<n;i++) { cin>>x; p[i*4+1].x=p[i*4+2].x=p[i*4+3].x=p[i*4+4].x=x; cin>>p[i*4+4].y>>p[i*4+3].y>>p[i*4+2].y>>p[i*4+1].y; } p[0].x=0,p[0].y=5; p[K].x=10,p[K].y=5; for(int i=0;i<=K;i++) for(int j=0;j<=K;j++) d[i][j]=INF; } void getd() { for(int i=0;i<=K;i++) for(int j=i+1;j<=K;j++) if(check(i,j)) d[i][j]=ojld(i,j); } void Floyd() { for(int k=0;k<=K;k++) for(int i=0;i<=K;i++) for(int j=0;j<=K;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); printf("%.2lf\n",d[0][K]); } int main() { init(); getd(); Floyd(); return 0; } -
0
//PowderHan的改进版
#include<bits/stdc++.h>
using namespace std;const int MAXN=100;
const double INF=999.0;
struct node
{
double x,y;
}p[MAXN];
int n,K;
double d[MAXN][MAXN];double inline ojld(int i,int j)
{
return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)
+(p[i].y-p[j].y)*(p[i].y-p[j].y));
}double det(double x1,double y1,double x2,double y2)//行列式
{
return x1*y2-x2*y1;
}
double cross(node p0,node p1,node p2)//叉积
{
double ans = det(p1.x-p0.x,p1.y-p0.y,p2.x-p0.x,p2.y-p0.y);
return ans;
}
bool check(int a,int b)//判断能否连通
{
if(p[a].x == p[b].x) return false;
for(int i = a+1;i < b;i++)
{
if(p[i].x == p[a].x || p[i].x == p[b].x) continue;
node temp;
if(i%4==1)
{
temp.x = p[i].x,temp.y = 10;
if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0)
return false;
}
if(i%4==0)
{
temp.x = p[i].x,temp.y = 0;
if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0)
return false;
}
if(i%4==2)
{
temp.x = p[i+1].x,temp.y = p[i+1].y;
if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0)
return false;
}
}
return true;
}void init()
{
double x;
cin>>n;
K=4*n+1;
for(int i=0;i<n;i++)
{
cin>>x;
p[i*4+1].x=p[i*4+2].x=p[i*4+3].x=p[i*4+4].x=x;
cin>>p[i*4+4].y>>p[i*4+3].y>>p[i*4+2].y>>p[i*4+1].y;
}
p[0].x=0,p[0].y=5;
p[K].x=10,p[K].y=5;
for(int i=0;i<=K;i++)
for(int j=0;j<=K;j++)
d[i][j]=INF;
}void getd()
{
for(int i=0;i<=K;i++)
for(int j=i+1;j<=K;j++)
if(check(i,j))
d[i][j]=ojld(i,j);
}void Floyd()
{
for(int k=0;k<=K;k++)
for(int i=0;i<=K;i++)
for(int j=0;j<=K;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
printf("%.2lf\n",d[0][K]);
}int main()
{
init();
getd();
Floyd();
return 0;
} -
0
区间DP的思路很容易就可以写出来
需要注意的是细节比较多，小数点和等号也比较诡异
判断能否联通直接斜率硬算就可以#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; struct wall{ double x; double a[5]; }q[22]; double minn[22][5]; int pan[22][22][5][5]; int main() { int n,i,j,u,k,v; double xie,now; memset(pan,0,sizeof(pan)); cin>>n; for(i=1;i<=n;i++) { cin>>q[i].x>>q[i].a[1]>>q[i].a[2]>>q[i].a[3]>>q[i].a[4]; } q[0].x=0; q[0].a[1]=q[0].a[2]=q[0].a[3]=q[0].a[4]=5; q[n+1].x=10; q[n+1].a[1]=q[n+1].a[2]=q[n+1].a[3]=q[n+1].a[4]=5; for(i=1;i<=n+1;i++) { for(k=0;k<i;k++) { for(j=1;j<=4;j++) for(u=1;u<=4;u++) { if(k==i-1) { pan[i][k][j][u]=1; continue; } xie=(q[i].a[j]-q[k].a[u])/(q[i].x-q[k].x); for(v=k+1;v<i;v++) { now=q[k].a[u]+xie*(q[v].x-q[k].x); if(now>=q[v].a[1]&&now<=q[v].a[2]) continue; if(now>=q[v].a[3]&&now<=q[v].a[4]) continue; break; } if(v>=i) pan[i][k][j][u]=1; } } } for(i=1;i<=n+1;i++) { for(k=0;k<i;k++) { for(j=1;j<=4;j++) { for(u=1;u<=4;u++) if(pan[i][k][j][u]) if(minn[i][j]!=0) minn[i][j]=min(minn[i][j],minn[k][u]+sqrt((q[i].x-q[k].x)*(q[i].x-q[k].x)+(q[i].a[j]-q[k].a[u])*(q[i].a[j]-q[k].a[u]))); else minn[i][j]=minn[k][u]+sqrt((q[i].x-q[k].x)*(q[i].x-q[k].x)+(q[i].a[j]-q[k].a[u])*(q[i].a[j]-q[k].a[u])); } } } printf("%.2lf",minn[n+1][2]); return 0; } -
0
思路：每个线段端点都来一发，判相交（叉积），连边（欧几里德距离），最短路。
这是改了4次 ，4次的代码啊，终于写出来了，不容易啊！！！
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<cmath> #define inf (118) #define eps (1e-8) using namespace std; struct POINT { double x,y; POINT operator + (POINT tm) { return (POINT) { x+tm.x,y+tm.y }; } POINT operator - (POINT tm) { return (POINT) { x-tm.x,y-tm.y }; } double operator * (POINT tm) { return x*tm.x-y*tm.y; } double operator ^ (POINT tm) { return x*tm.y-y*tm.x; } }; struct EDGE { int u,v; double dis; }; int n; int pcnt,pst,ped; double lis[150]; POINT pset[150]; int lnset[30][5]; vector<EDGE> eset[150]; int sign (double tm) { if (fabs(tm)<eps) return 0; else return tm>0?1:-1; } double distant (POINT tma,POINT tmb) { return sqrt((tma.x-tmb.x)*(tma.x-tmb.x)+(tma.y-tmb.y)*(tma.y-tmb.y)); } bool csjudge (POINT tma,POINT tmb,POINT tmc,POINT tmd) { if (sign(((tmc-tma)^(tmd-tma))*((tmc-tmb)^(tmd-tmb)))>=0) return 0; if (sign(((tma-tmc)^(tmb-tmc))*((tma-tmd)^(tmb-tmd)))>=0) return 0; return 1; } int pmake (double x,double y) { pset[++pcnt]=(POINT) { x,y }; return pcnt; } void emake (int tma,int tmb) { POINT tmpa=pset[tma],tmpb=pset[tmb]; double dis=distant(tmpa,tmpb); eset[tma].push_back((EDGE) {tma,tmb,dis}); return; } void spfa (int p) { queue<int> qu; bool vis[150]; qu.push(p); memset(lis,inf,sizeof(lis)),lis[p]=0; memset(vis,0,sizeof(vis)),vis[p]=1; while(!qu.empty()) { int now=qu.front(); qu.pop(); for(int i=0; i<eset[now].size(); i++) { int nxt=eset[now][i].v; double dis=eset[now][i].dis; if (lis[now]+dis<lis[nxt]) { if (!vis[nxt]) { qu.push(nxt); vis[nxt]=1; lis[nxt]=lis[now]+dis; } lis[nxt]=lis[now]+dis; } } vis[now]=0; } return; } bool judge (int tma,int tmb) { POINT tmpa=pset[tma],tmpb=pset[tmb]; for(int i=1; i<=n; i++) { POINT pa=pset[lnset[i][1]],pb=pset[lnset[i][2]], pc=pset[lnset[i][3]],pd=pset[lnset[i][4]]; POINT lowp=(POINT) {pa.x,0},highp=(POINT) {pa.x,10}; if (tmpa.x>=pa.x||tmpb.x<=pa.x) continue; if (csjudge(tmpa,tmpb,lowp,pa)) return 0; if (csjudge(tmpa,tmpb,pb,pc)) return 0; if (csjudge(tmpa,tmpb,pd,highp)) return 0; } return 1; } void clear () { pcnt=pst=ped=0; memset(pset,0,sizeof(pset)); memset(lnset,0,sizeof(lnset)); memset(eset,0,sizeof(eset)); } int main () { scanf("%d",&n); for(int i=1; i<=4; i++) lnset[0][i]=pmake(0,5),lnset[n+1][i]=pmake(10,5); pst=lnset[0][1],ped=lnset[n+1][1]; double x,y; for(int i=1; i<=n; i++) { scanf("%lf",&x); for(int j=1; j<=4; j++) { scanf("%lf",&y); lnset[i][j]=pmake(x,y); } } for(int i=1; i<=n+1; i++) for(int j=0; j<i; j++) for(int o=1; o<=4; o++) for(int g=1; g<=4; g++) if (judge(lnset[j][g],lnset[i][o])) emake(lnset[j][g],lnset[i][o]),emake(lnset[i][o],lnset[j][g]); spfa(pst); printf("%.2f\n",lis[ped]); return 0; }
-
0
superczsyz LV 5 @ 2016-05-03 16:18:59
典型的计算几何。构造一个图，把所有互相能看见的点对连接成边，生成一个邻接矩阵，随后最短路即可。
如何判断点对之间能否相互看见呢？假定它们相连成边 e，只需遍历所有墙，看看是否与边 e 相交即可。var
a:array[0..30,0..4]of real;
i,j,jj,k,m,n:Longint;
p:real;
dis:array[0..30,0..4]of real;
function len(i,j,x,y:Longint):real;
begin
exit(sqrt(sqr(a[i,j]-a[x,y])+sqr(a[i,0]-a[x,0])));
end;
function can(x,y,x1,y1:Longint):boolean;{看x边上的y点与x1边上的y1点能否看到｝
var
i,j:longint;
yy:real;
begin
for i:=x+1 to x1-1 do
begin
if a[x1,y1]=a[x,y] then yy:=a[x,y]
else
yy:=(a[i,0]-a[x,0])*(a[x1,y1]-a[x,y])/(a[x1,0]-a[x,0])+a[x,y];
if not ( ((yy>=a[i,1])and(yy<=a[i,2]))or ((yy>=a[i,3])and(yy<=a[i,4])))
then exit(false);
end;
exit(true);
end;
begin
read(n);
a[0,0]:=0;
a[n+1,0]:=10;
for i:=1 to 4 do
begin
a[0,i]:=5;
a[n+1,i]:=5;
end;
for i:=1 to n do
for j:=0 to 4 do
read(a[i,j]);for I:=1 to n+1 do
begin
for j:=1 to 4 dofor jj:=0 to i-1 do
for k:=1 to 4 do
if can(jj,k,i,j) then
begin
p:=dis[jj,k]+len(jj,k,i,j);
if (dis[i,j]=0)or(dis[i,j]>p) then
dis[i,j]:=p;
end;end;
writeln(dis[n+1,1]:0:2);
end. -
0
总体思路 能互相看到的两点之间的边加入图 然后是最短路问题
Floyd dij全秒杀 不要忘了两头能直接相连
虽说是水题，但技术还是不行啊。。交了好几次。。全细节错误。。program dij; var w:array[0..100,0..100] of double; xy:array[0..25,0..5] of double; i,j,k,n,p:integer; function line(x1,y1,x2,y2:double):boolean; var i:integer; b,k,t:double; begin if x1=x2 then exit(false); k:=(y1-y2)/(x1-x2); b:=y1-k*x1; for i:=1 to n do begin t:=k*xy[i,0]+b; if ((xy[i,0]>x1) and (xy[i,0]<x2)) or ((xy[i,0]<x1) and (xy[i,0]>x2)) then if (t<xy[i,1]) or (t>xy[i,4]) or ((t>xy[i,2]) and (t<xy[i,3]))then exit(false); end; exit(true); end; function dis(x1,y1,x2,y2:double):double; begin exit(sqrt(sqr(x1-x2)+sqr(y1-y2))); end; begin read(n); for i:=1 to n do for j:=0 to 4 do read(xy[i,j]); for i:=1 to 4*n+2 do for j:=1 to 4*n+2 do if i<>j then w[i,j]:=99 else w[i,j]:=0; xy[0,0]:=0;xy[0,1]:=5;xy[n+1,0]:=10;xy[n+1,1]:=5; for i:=0 to n+1 do if (i=0) or (i=n+1) then begin for j:=1 to n do for k:=1 to 4 do if line(xy[i,0],xy[i,1],xy[j,0],xy[j,k]) then begin if i=0 then begin w[1,(j-1)*4+1+k]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]); w[(j-1)*4+1+k,1]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]); end else begin w[4*n+2,(j-1)*4+1+k]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]); w[(j-1)*4+1+k,4*n+2]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]); end end end else for p:=1 to 4 do for j:=1 to n do for k:=1 to 4 do if line(xy[i,0],xy[i,p],xy[j,0],xy[j,k]) then begin w[(i-1)*4+1+p,(j-1)*4+1+k]:=dis(xy[i,0],xy[i,p],xy[j,0],xy[j,k]); w[(j-1)*4+1+k,(i-1)*4+1+p]:=dis(xy[i,0],xy[i,p],xy[j,0],xy[j,k]); end; if line(xy[0,0],xy[0,1],xy[n+1,0],xy[n+1,1]) then w[1,4*n+2]:=dis(xy[0,0],xy[0,1],xy[n+1,0],xy[n+1,1]); for k:=1 to 4*n+2 do for i:=1 to 4*n+2 do for j:=1 to 4*n+2 do if w[i,j]>w[i,k]+w[k,j] then w[i,j]:=w[i,k]+w[k,j]; writeln(w[1,4*n+2]:0:2); end. -
0
wang_yanheng LV 10 @ 2015-04-12 16:42:42
典型的计算几何。只需构造一个图，把所有互相能看见的点对连接成边，生成一个邻接矩阵，随后最短路即可。有人说用 floyd 或 SPFA，好像没必要吧，毕竟是点对点且无负权，Dijkstra 秒杀。
如何判断点对之间能否相互看见呢？假定它们相连成边 e，只需遍历所有墙，看看是否与边 e 相交即可。由于这道题的墙都是竖直的，所以还算好处理，直接解析式算得了，没必要用向量叉积那种方法。
最后上代码#include <stdio.h>
#include <math.h>
#include <limits.h>#define SQR(a) ((a)*(a))
#define X 0
#define Y 1
#define Y1 1
#define Y2 2double vertices[100][2];
double edges[80][3];
double map[100][100];double value[100];
int used[100];void addEdge(int index,double x,double y1,double y2){
edges[index][X]=x;
edges[index][Y1]=y1;
edges[index][Y2]=y2;
}int intersect(int indexP1,int indexP2,int indexEdge){
double x1,x2,y1,y2,y3,y4;
double k,b,x;x1=vertices[indexP1][X],x2=vertices[indexP2][X];
y1=vertices[indexP1][Y],y2=vertices[indexP2][Y];
x=edges[indexEdge][X];
y3=edges[indexEdge][Y1],y4=edges[indexEdge][Y2];k=(y2-y1)/(x2-x1);
b=y1-k*x1;
if(k*x+b>y3 && k*x+b<y4)
return 1;
else
return 0;
}int main(){
int num,numVertex,numEdge;
int i,k,n,m,flag,source;
double x,min;/*read data*/
scanf("%d",&num);
numVertex=num*4+2;
numEdge=num*3;
vertices[0][X]=0;
vertices[0][Y]=5;
for(i=n=1,m=0;i<=num;i++){
scanf("%lf",&x);
for(k=0;k<4;k++){
vertices[n][X]=x;
scanf("%lf",&vertices[n][Y]);
n++;
}
addEdge(m,x,0,vertices[n-4][Y]);
addEdge(m+1,x,vertices[n-3][Y],vertices[n-2][Y]);
addEdge(m+2,x,vertices[n-1][Y],10);
m+=3;
}
vertices[numVertex-1][X]=10;
vertices[numVertex-1][Y]=5;/*create a map*/
for(i=0;i<numVertex;i++){
for(k=0;k<numVertex;k++)
map[i][k]=0;
}
for(i=0;i<numVertex;i++){
for(k=i+1;k<numVertex;k++){
//try to connect them together
if(vertices[i][X]==vertices[k][X])
continue;
flag=1;
for(n=0;n<numEdge;n++){
if(vertices[i][X]>=edges[n][X])
continue;
if(vertices[k][X]<=edges[n][X])
break;
if(intersect(i,k,n)){
flag=0;
break;
}
}
if(flag){
map[i][k]=map[k][i]=sqrt(
SQR(vertices[i][X]-vertices[k][X]) + SQR(vertices[i][Y]-vertices[k][Y])
);
}
}
}/*shortest path*/
for(i=0;i<numVertex;i++){
value[i]=LONG_MAX;
used[i]=0;
}
value[0]=0;
for(i=0;i<numVertex;i++){
min=LONG_MAX;
for(k=0;k<numVertex;k++){
if(!used[k] && min>value[k]){
min=value[k];
source=k;
}
}
used[source]=1;
for(k=0;k<numVertex;k++){
if(map[source][k]>0 && value[k]>value[source]+map[source][k])
value[k]=value[source]+map[source][k];
}
}/*output solution*/
printf("%.2lf\n",value[numVertex-1]);return 0;
} -
0
这是什么叼情况？
测试数据 #0: WrongAnswer, time = 15 ms, mem = 804 KiB, score = 0
测试数据 #1: Accepted, time = 15 ms, mem = 800 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 808 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 804 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 804 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 804 KiB, score = 10
WrongAnswer, time = 76 ms, mem = 808 KiB, score = 50 -
0
87443555seer LV 8 @ 2014-04-02 18:43:34
为什么过不了！！！！！各大神!!!!!
readln(n);
for i:=1 to n do readln(l[i],a[1,i],b[1,i],a[2,i],b[2,i]);
inc(n);
a[1,0]:=5; b[1,0]:=5; a[2,0]:=5; b[2,0]:=5; l[0]:=0;
a[1,n]:=5; b[1,n]:=5; a[2,n]:=5; b[2,n]:=5; l[n]:=10;
for i:=0 to n do l[i]:=l[i]*100;
//------------------------------------
for i:=n-1 downto 0 do begin
g:=f; fillchar(f,sizeof(f),$7f);
for d1:=1 to 2 do
for j:=trunc(a[d1,i]*100) to trunc(b[d1,i]*100) do
for d2:=1 to 2 do
for k:=trunc(a[d2,i+1]*100) to trunc(b[d2,i+1]*100) do
f[j]:=min(f[j],g[k]+dis(l[i],j,l,k));
end; -
0
readln(n);
for i:=1 to n do readln(l[i],a[1,i],b[1,i],a[2,i],b[2,i]);
inc(n);
a[1,0]:=5; b[1,0]:=5; a[2,0]:=5; b[2,0]:=5; l[0]:=0;
a[1,n]:=5; b[1,n]:=5; a[2,n]:=5; b[2,n]:=5; l[n]:=10;
for i:=0 to n do l[i]:=l[i]*100;
//------------------------------------
for i:=n-1 downto 0 do begin
g:=f; fillchar(f,sizeof(f),$7f);
for d1:=1 to 2 do
for j:=trunc(a[d1,i]*100) to trunc(b[d1,i]*100) do
for d2:=1 to 2 do
for k:=trunc(a[d2,i+1]*100) to trunc(b[d2,i+1]*100) do
f[j]:=min(f[j],g[k]+dis(l[i],j,l,k));
end; -
0
JackDavid135 LV 8 @ 2014-02-02 21:31:20
为何使用spfa倒数第二个点死活过不去。。
-
0
-
1159305727 @ 2014-10-31 14:53:22
nmd,你不要在这个网站上捣乱好不好？
-
JokerJQKA @ 2015-08-12 18:47:27
你脑洞小苹果了？？？
-
Jessy @ 2016-09-04 21:47:15
有意思么？
-
-
0
jiaoyunhao LV 10 @ 2012-07-17 16:10:14
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
发一个丑陋的DP
var
n,i,j,k:longint;
x,a1,b1,a2,b2:array[1..30] of double;
f:array[1..20,1..4] of double;
ans:double;function dis(x1,y1,x2,y2:double):double;
begin
exit(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
end;function min(a,b:double):double;
begin
if a>b then exit(b) else exit(a);
end;function pan(i,j:longint;x1,y1,x2,y2:double):boolean;
var
p:longint;
k,b:double;
begin
k:=(y2-y1)/(x2-x1);
b:=y1-k*x1;
for p:=i+1 to j-1 do
if not (((k*x[p]+b=a1[p])) or ((k*x[p]+b=a2[p]))) then
exit(false);
exit(true);
end;function make(p:longint;y:double):double;
var
i:longint;
pa:boolean;
k,ans:double;
begin
k:=(y-5)/x[p];
pa:=true;
for i:=1 to p-1 do
if not (((k*x[i]+5=a1[i])) or ((k*x[i]+5=a2[i]))) then
begin
pa:=false;
break;
end;
if pa then exit(dis(0,5,x[p],y));
ans:=maxlongint;
for i:=1 to p-1 do
begin
if pan(i,p,x[i],a1[i],x[p],y) then
ans:=min(ans,f+dis(x[i],a1[i],x[p],y));
if pan(i,p,x[i],b1[i],x[p],y) then
ans:=min(ans,f+dis(x[i],b1[i],x[p],y));
if pan(i,p,x[i],a2[i],x[p],y) then
ans:=min(ans,f+dis(x[i],a2[i],x[p],y));
if pan(i,p,x[i],b2[i],x[p],y) then
ans:=min(ans,f+dis(x[i],b2[i],x[p],y));
end;
exit(ans);
end;begin
readln(n);
for i:=1 to n do
readln(x[i],a1[i],b1[i],a2[i],b2[i]);
f[1,1]:=dis(0,5,x[1],a1[1]);
f[1,2]:=dis(0,5,x[1],b1[1]);
f[1,3]:=dis(0,5,x[1],a2[1]);
f[1,4]:=dis(0,5,x[1],b2[1]);
for i:=2 to n do
begin
f:=make(i,a1[i]);
f:=make(i,b1[i]);
f:=make(i,a2[i]);
f:=make(i,b2[i]);
end;
x[n+1]:=10;
writeln(make(n+1,5):0:2);
end.
PowderHan
LV 10
@ 2017-05-07 12:47:15
