编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

茶几+spfa

dp+叉积

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Accepted 有效得分：100 有效耗时：72ms

这题暴力解,一次A!

将每个坐标值*100再取整,因为是要精确2位嘛.

虽然时间慢点,72ms...囧...

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;

我无语了

。。。居然一次就过了。。建了一个囧图然后SPFA。。

囧死掉，细节啊，交了6次才过……

其中有2次是因为忘保留两位小数，有3次是因为忘关文件操作……

本题AC率被我活生生刷下1%……

跨立试验 + SPFA

Dijkstra+判断直线相交，一次AC。。。

DP

设f(i)为标号i的节点到初始节点的长度

f(i)=min(f(j)+dis(i,j)(i,j可达))

程序大概40～50行左右，我写的比较冗长47行

program P1013;

var

x:array[-1..20]of real;

a,f:array[-1..80]of real;

n,i,j:longint;

ans,dis:real;

s:boolean;

function min(b,c:real):real;

begin

if b=0

then lb:=b shr 2

else lb:=-1;

lc:=c shr 2;pd:=true;

k:=(a-a[c])/(x[lb]-x[lc]);

for l:=lb+1 to lc-1 do

begin

d:=a+k*(x[l]-x[lb]);

if (da[4*l+3])

then begin

pd:=false;

break;

end;

end;

dis:=sqrt(sqr(a-a[c])+sqr(x[lb]-x[lc]));

end;

begin

readln(n);

x[-1]:=0;a[-1]:=5;x[n]:=10;a[4*n]:=5;

for i:=0 to n-1 do

readln(x[i],a,a,a,a);

for i:=0 to 4*n do

f[i]:=1e10;

for i:=0 to 4*n do

for j:=-1 to 4*(i shr 2)-1 do

if pd(j,i)

then f[i]:=min(f[i],dis+f[j]);

end.

程序千万不要直接考哦！少了一个语句

WS的打了90+行....结果1次ms..

第一个一遍AC的 o(∩_∩)o...

简单模拟 加一个判断函数即可

相似三角+DP为什么第四个点比正确答案少0.05...

细节问题

http://hi.baidu.com/%CB%D5%CC%DAsauterne

shit 一个变量打错了

简单的DP，如果能够从(x1,y1)不穿墙直接到达(x2,y2)（x2>x1），那么

dis[x1,y1]=min{dis[x1,y1],dis[x2,y2]+len}，其中len是(x1,y1)到(x2,y2)的距离

可惜我看错了题目，以为n

叉积即可

终于AC！！！

就是有点麻烦而已。

一次搞定：D 89行……

起点编到一半才想起来 于是加了个数列第-1项 但 -1div4=1div4=0所以起点和其他点的联通情况最好单独判断。

附判断函数：

var

cost:array[-1..80,-1..80]of real;

x,y:array[-1..80]of real;

function bool(a,b:integer):boolean;

var

i,j:integer;

begin

for i:=(a div 4)+1 to (b div 4)-1 do

begin

if (y-y[a])/(x-x[a])>(y-y[a])/(x-x[a]) then exit(false);

if ( (y-y[a])/(x-x[a])(y-y[a])/(x-x[a]) ) then exit(false);

if (y-y[a])/(x-x[a])(y-y[a])/(x-x[a]) then exit(false);

if ( (y-y[a])/(x-x[a])(y-y[a])/(x-x[a]) ) then exit(false);

if (y-y[a])/(x-x[a])

type

dot=record

x,y:double;

end;

line=record

a,b:dot;

end;

var

n,p,cl,op:longint;

d:array[0..100]of dot;

l:array[0..70]of line;

fir:array[0..100]of longint;

dist:array[0..100]of double;

used:array[0..100]of boolean;

w:array[0..100*100]of double;

u,last,q:array[0..100*100]of longint;

function cj(a,b,c:dot):double;

begin

cj:=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

end;

function can(a,b:dot):boolean;

var

i:longint;

begin

for i:=1 to ((n-2)div 4)*3 do

if (cj(a,b,l[i].a)*cj(a,b,l[i].b)

额。。不是很难，但是要细心一点。

我自己中的招：没有判断能否从起点直接到达。