- 强墙
- 2009-03-28 14:53:55 @
谁能救救我?
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 条评论
-
hahacool LV 10 @ 2009-05-23 20:46:54
sorry,没时间观赏您的程序。。。
总之把每个端点记作一个图的节点,判断节点间是否连通,这样预处理之后直接dijkstra就可以。。。【当然你喜欢spfa,bellman-ford还是BFS也随你,反正都不tle的~】
- 1