/ Vijos / 讨论 / 强墙 /

我不会,谁能救救我?

谁能救救我?

var

x,y:array[0..81]of real;

n,i,j,k,t:integer;

tmp:real;

f:boolean;

g:array[0..81,0..81]of real;

function chaji(x1,y1,x2,y2:real):real;

begin

exit(x1*y2-x2*y1);

end;

function dist(x1,y1,x2,y2:real):real;

begin

exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));

end;

begin

readln(n);

for i:=1 to n do

begin

read(tmp);

for j:=1 to 4 do

begin

x[4*(i-1)+j]:=tmp;

read(y[4*(i-1)+j]);

end;

readln;

end;

y[0]:=5;

x[4*n+1]:=10;

y[4*n+1]:=5;

for i:=0 to 4*n+1 do

for j:=0 to 4*n+1 do

g:=100000;

for i:=0 to 4*n do

for j:=i+1 to 4*n+1 do

begin

f:=true;

for k:=(i + 3) div 4 + 1 to (j + 3) div 4 - 1 do

begin

f:=false;

for t:=1 to 2 do

if (chaji(x[j]-x[i],y[j]-y[i],x[(k-1)*4+2*t-1]-x[i],y[(k-1)*4+2*t-1]-y[i])>=0)

and (chaji(x[j]-x[i],y[j]-y[i],x[(k-1)*4+2*t]-x[i],y[(k-1)*4+2*t]-y[i])

1 条评论

  • @ 2009-05-23 20:46:54

    sorry,没时间观赏您的程序。。。

    总之把每个端点记作一个图的节点,判断节点间是否连通,这样预处理之后直接dijkstra就可以。。。【当然你喜欢spfa,bellman-ford还是BFS也随你,反正都不tle的~】

  • 1

信息

ID
1013
难度
6
分类
计算几何 点击显示
标签
(无)
递交数
2269
已通过
532
通过率
23%
被复制
15
上传者