98 条题解
-
0
jiaoyunhao LV 10 @ 2012-08-08 21:40:22
VijosNT Mini 2.0.5.7 Special for Vijos
编译通过...
├ 测试数据 01：答案正确... (0ms, 604KB)
├ 测试数据 02：答案正确... (0ms, 604KB)
├ 测试数据 03：答案正确... (0ms, 604KB)
├ 测试数据 04：答案正确... (1ms, 604KB)
├ 测试数据 05：答案正确... (1ms, 604KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 3ms / 604KB这种题目1A是必须的
-
0
忘记这题没有“多组数据”了
传了三遍 = =
LX的程序怎么都这么高？
哈，我的也差不多 = =My Code:
var
n,a,b,s,t0: longint;
p: array[1..100,1..4] of point;
dis: array[1..100,1..4] of real;
t: array[1..100] of longint;
used: array[1..100,1..4] of boolean;function d(p1,p2: point): real;
begin
exit(sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y)));
end;function Another(var p1,p2,p3: point): point;
var
t: point;
begin
if (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y)=0 then begin
t:=p1; p1:=p2; p2:=t;
end else
if (p1.x-p3.x)*(p2.x-p3.x)+(p1.y-p3.y)*(p2.y-p3.y)=0 then begin
t:=p3; p3:=p2; p2:=t;
end;
Another.x:=p1.x+p3.x-p2.x;
Another.y:=p1.y+p3.y-p2.y;
end;procedure init;
var
i,j: integer;
begin
readln(s,t0,a,b);
for i:= 1 to s do begin
for j:= 1 to 3 do read(p.x,p.y);
readln(t[i]);
p:=Another(p,p,p);
end;
end;function dijkstra: real;
var
i,j,k,l1,l2: integer;
min,q: real;
begin
fillchar(used,sizeof(used),0);
for i:= 1 to s do
for j:= 1 to 4 do dis:=1e38;
for i:= 1 to 4 do dis[a,i]:=0;
for i:= 1 to s*4 do begin
min:=1e37;
for j:= 1 to s do
for k:= 1 to 4 do
if (not used[j,k]) and (dis[j,k] -
0
Floyd 数据弱弱
procedure g(n,a,b,c:integer);
begin
if (st[n,a,1]-st[n,c,1])*
(st[n,a,1]-st[n,b,1])+
(st[n,a,2]-st[n,c,2])*
(st[n,a,2]-st[n,b,2])=0 then
begin
st[n,4,1]:=
st[n,b,1]+
st[n,c,1]-st[n,a,1];
st[n,4,2]:=
st[n,b,2]+
st[n,c,2]-
st[n,a,2];
end;
end;function dis(i1,j1,i2,j2:integer):real;
begin
dis:=sqrt(
sqr(st[i1,j1,1]-
st[i2,j2,1])+
sqr(st[i1,j1,2]-
st[i2,j2,2]
)
);
if i1=i2 then
dis:=dis*ct[i1]
else
dis:=dis*t;
end;procedure getvec(n:integer);
begin
g(n,1,2,3);
g(n,1,3,2);
g(n,2,1,3);
g(n,2,3,1);
g(n,3,1,2);
g(n,3,2,1);
end;var ki,kj,ii,ij,ji,jj:integer;
begin
read(s,t,a,b);
n:=s;
for i:=1 to s do
begin
for j:=1 to 3 do
read(st,st);
getvec(i);
read(ct[i]);
end;
fillchar(d,sizeof(d),0);for ii:=1 to n do
for ij:=1 to 4 do
for ji:=1 to n do
for jj:=1 to 4 do
d[ii,ij,ji,jj]:=
dis(ii,ij,ji,jj);for ki:=1 to n do
for kj:=1 to 4 do
for ii:=1 to n do
for ij:=1 to 4 do
for ji:=1 to n do
for jj:=1 to 4 do
if (d[ii,ij,ji,jj]=0)
or (d[ii,ij,ji,jj]>
d[ii,ij,ki,kj]+
d[ki,kj,ji,jj]) then
d[ii,ij,ji,jj]:=
d[ii,ij,ki,kj]+
d[ki,kj,ji,jj];
ans:=maxlongint;
for i:=1 to 4 do
for j:=1 to 4 do
if d[a,i,b,j] -
0
program v1119;
var
f:array[1..400,1..400]of real;
t:array[1..400]of longint;
x,y:array[1..4,1..100]of longint;
b:array[1..400]of boolean;
dist,p:array[1..400]of real;
s,t1,a,b1,i,j,k,q:longint;
min,min1:real;procedure swap(var x,y:longint);
var k:longint;
begin
k:=x;
x:=y;
y:=k;
end;begin
read(s,t1,a,b1);
if a=b1 then begin writeln('0.00');halt;end;
for i:=1 to s do
read(x[1][i],y[1][i],x[2][i],y[2][i],x[3][i],y[3][i],t[i]);
for j:=1 to s do
begin
for i:=1 to 3 do
begin
if not((x[1,j]-x[3,j])*(x[1,j]-x[2,j])+(y[1,j]-y[3,j])*(y[1,j]-y[2,j])=0) then
begin
swap(x[1,j],x[2,j]);
swap(y[1,j],y[2,j]);
end else break;
if not((x[1,j]-x[3,j])*(x[1,j]-x[2,j])+(y[1,j]-y[3,j])*(y[1,j]-y[2,j])=0) then
begin
swap(x[2,j],x[3,j]);
swap(y[2,j],y[3,j]);
end else break;
end;
x[4,j]:=x[2,j]+x[3,j]-x[1,j];
y[4,j]:=y[2,j]+y[3,j]-y[1,j];
end;
for i:=1 to s do
begin
for j:=1 to 4 do
for k:=1 to 4 do
f[4*(i-1)+j,4*(i-1)+k]:=sqrt(sqr(x[j,i]-x[k,i])+sqr(y[j,i]-y[k,i]))*t[i];
end;
for i:=1 to 4*s do
begin
for j:=1 to 4*s do
if f=0 then
if (i mod 40)and(j mod 40) then
f:=sqrt(sqr(x[i mod 4,(i-1)div 4+1]-x[j mod 4,(j-1)div 4+1])+sqr(y[i mod 4,(i-1)div 4+1]-y[j mod 4,(j-1)div 4+1]))*t1
else if (i mod 4=0)and(j mod 4 0) then
f:=sqrt(sqr(x[4,(i-1)div 4+1]-x[j mod 4,(j-1)div 4+1])+sqr(y[4,(i-1)div 4+1]-y[j mod 4,(j-1)div 4+1]))*t1
else if (i mod 40)and(j mod 4=0) then
f:=sqrt(sqr(x[i mod 4,(i-1)div 4+1]-x[4,(j-1)div 4+1])+sqr(y[i mod 4,(i-1)div 4+1]-y[4,(j-1)div 4+1]))*t1
else f:=sqrt(sqr(x[4,(i-1)div 4+1]-x[4,(j-1)div 4+1])+sqr(y[4,(i-1)div 4+1]-y[4,(j-1)div 4+1]))*t1;
end;
min1:=1e30;
for k:=1 to 4 do
begin
fillchar(dist,sizeof(dist),0);
fillchar(b,sizeof(b),0);
fillchar(p,sizeof(p),0);
for i:=1 to 4*s do
dist[i]:=f[4*(a-1)+k,i];
min:=1e30;
for i:=1 to 4*s do
if (dist[i]min+f[q,j] then dist[j]:=min+f[q,j];
end;
min:=1e30;
for j:=1 to 4*s do
if not b[j] then
begin
if dist[j] -
0
zhaoyifeng LV 8 @ 2009-10-30 13:13:05
var
x,y:array[1..100,1..4] of longint;
pl:array[1..100,1..4] of real;
pt:boolean;
ppt:array[1..100,1..4] of boolean;
min:real;
df:array[1..100] of longint;
j1,i,j,k1,l,i12,n,s,t,a,b,k2,k,p1,p2,p3,p:longint;
f:array[1..100,1..4,1..100,1..4] of real;
function try(a,b,c:longint):integer;
begin
if a+b=c then exit(3)
else if a+c=b then exit(2)
else if b+c=a then exit(1);
end;
beginfor i12:=1 to 1 do
begin
readln(s,t,a,b);
for i:= 1 to s do
begin
readln(x,y,x,y,x,y,df[i]);p1:=sqr(x-x)+sqr(y-y);
p2:=sqr(x-x)+sqr(y-y);
p3:=sqr(x-x)+sqr(y-y);
p:=try(p1,p2,p3);
if p=1 then begin
x:=x+x-x;
y:=y+y-y;
end
else if p=2 then
begin
x:=x+x-x;
y:=y+y-y;
end
else if p=3 then begin
x:=x+x-x;
y:=y+y-y;
end;
end;
fillchar(f,sizeof(f),0);
for i:=1 to s do
for k1:=1 to 4 do
for j:=1 to s do
for k2:=1 to 4 do
f:=sqrt(sqr(x-x[j,k2])+sqr(y-y[j,k2]));
for i:=1 to s do
for k1:=1 to 4 do
pl:=999999;
for i:=1 to 4 do pl[a,i]:=0;
fillchar(ppt,sizeof(ppt),true);
j:=a;k:=1;
ppt[j,k]:=false;
while (jb) do
begin
min:=100000;
k1:=k;j1:=j;
for i:=1 to 4 do
if (ppt[j,i]) and (pl[j,k]+f[j,k,j,i]*df[j] -
0
var
n,i,j,k,l,x1,x2,x3,xx1,xx2,xx3,ii,jj,kk,k1,k2:integer;
s,t,a,b,che:integer;
g:array[1..100,1..100]of real;
dd:array[1..100,1..2]of integer;
d:array[1..4,1..2]of integer;
min:real;
ok:boolean;
begin
readln(s,t,a,b);
for ii:=1 to 40 do
for jj:=1 to 40 do g[ii,jj]:=99999;
for j:=0 to s-1 do
begin
for k:=1 to 3 do read(d[k,1],d[k,2]); read(che);
ok:=true;
for x1:=1 to 3 do
for x2:=1 to 3 do
if (x1x2)and(ok) then
begin
x3:=6-x1-x2;
if (d[x1,1]-d[x2,1])*(d[x1,1]-d[x2,1])+(d[x1,2]-d[x2,2])*(d[x1,2]-d[x2,2])
+(d[x2,1]-d[x3,1])*(d[x2,1]-d[x3,1])+(d[x2,2]-d[x3,2])*(d[x2,2]-d[x3,2])
=(d[x1,1]-d[x3,1])*(d[x1,1]-d[x3,1])+(d[x1,2]-d[x3,2])*(d[x1,2]-d[x3,2]) then
begin xx1:=x1; xx2:=x2; xx3:=x3; ok:=false; end;
end;
d[4,1]:=d[xx1,1]+d[xx3,1]-d[xx2,1];
d[4,2]:=d[xx1,2]+d[xx3,2]-d[xx2,2];
for ii:=1 to 4 do
dd[j*4+ii]:=d[ii];for ii:=1 to 3 do
for jj:=ii+1 to 4 do
begin
g[j*4+ii,j*4+jj]:=sqrt((d[ii,1]-d[jj,1])*(d[ii,1]-d[jj,1])+(d[ii,2]-d[jj,2])*(d[ii,2]-d[jj,2]))*che;
g[j*4+jj,j*4+ii]:=g[j*4+ii,j*4+jj];
end;
end;for ii:=0 to s-1 do
for jj:=ii+1 to s-1 do
for k1:=1 to 4 do
for k2:=1 to 4 do
begin
g[ii*4+k1,jj*4+k2]:=sqrt((dd[ii*4+k1,1]-dd[jj*4+k2,1])*(dd[ii*4+k1,1]-dd[jj*4+k2,1])+(dd[ii*4+k1,2]-dd[jj*4+k2,2])*(dd[ii*4+k1,2]-dd[jj*4+k2,2]))*t;
g[jj*4+k2,ii*4+k1]:=g[ii*4+k1,jj*4+k2];
end;
for kk:=1 to s*4 do
for ii:=1 to s*4 do
for jj:=1 to s*4 do
if g[ii,kk]+g[kk,jj] -
0
song19931218 LV 9 @ 2009-10-27 21:48:33
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms由向量知识可以解决题目中的第一个障碍：
根据矩形中已知的三点坐标求第四点的坐标；
接着就是建图：我的做法是将每个城市拆成四个点，所以极限数据是图中共有1200个点；
接着便是求最短路径，我分了是种情况，调用了四次spfa,时间肯定不超。。。。。
最后输出最优解即可。。 -
0
唯一背的出的图论算法————————FLOYD！
NOIP的题数据都很弱，包括07的树网的核，用FLOYD一样过
数学处理很简单，还好没有出小错误
PS：一开始建图建错了。。。晕
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
将给定3点连成3条向量，用点乘判断垂直点，再用向量加法即可求出第4点……私认为比较简洁……
建立坐标系代码：for i:=1 to n do begin
for j:=1 to 3 do begin
read(x);
read(y);
end;
readln(tr[i]);
for j:=1 to 2 do begin
lsx[j]:=x-x;
lsy[j]:=y-y;
end;
lsx[3]:=x-x;
lsy[3]:=y-y;
flagj:=0;
for j:=1 to 2 do begin
ls1:=lsx[j]*lsx[j+1]+lsy[j]*lsy[j+1];
if ls1=0 then begin
flagj:=j;
break;
end;
end;
if flagj=0 then begin
ls1:=lsx[3]*lsx[1]+lsy[3]*lsy[1];
if ls1=0 then flagj:=3;
end;
if flagj=3 then ls2:=1 else ls2:=flagj+1;
ls1:=flagj;
x:=x-lsx[ls1]+lsx[ls2];
y:=y-lsy[ls1]+lsy[ls2];
end; -
0
这是我到目前为止写的最麻烦的一道题
代码贴出来就是为了让大牛们BS的
也是为了提醒我要好好学习数学............
看我求第四个点的过程就知道我是什么数学水平了........
好久没写过这么长这么X的程序了
题目就是一个转化加上Dijkstra
把每个城市抽象成4个点即可
求的时候用向量即可 简单向量加法
我写麻烦了..........
O(4^3*N^2)
另：有a=b情况 大家注意
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
var
a,de:array[1..400,1..400] of real;
c:array[1..400,1..2] of real;
d:array[1..400] of longint;
t:array[1..400] of real;
vis:array[1..400] of boolean;
x,y:array[1..3] of real;
k2,b2,x1,vp,min1,k1,b1,l1,wy,wx,s1,kx,ky:real;
er,q,bg,ed,n,m,i,j,k,l:longint;
function max(x,y:real):real;
begin
if x>y then exit(x)
else exit(y);
end;
function min(x,y:real):real;
begin
if x>y then exit(y)
else exit(x);
end;
procedure change;
begin
for j:=1 to 3 do
for k:=1 to 3 do
if (jk) then
for l:=1 to 3 do
if (lj) and (lk) then
if abs((x[j]-x[k])*(x[k]-x[l])+(y[j]-y[k])*(y[k]-y[l]))
0.001
then begin
k1:=(wy-y[k])/(wx-x[k]);
b1:=wy-k1*wx;
l1:=s1/sqrt(1+sqr(k1));
if k10 then k2:=-1/k1;
b2:=wy-k2*wx;
if k1x[k] then kx:=wx+l1
else kx:=wx-l1;
end
else
if (x[k]*k2+b2)>0 then
begin
if k2>0 then kx:=wx-l1
else kx:=wx+l1;
ky:=kx*k1+b1;
end
else
if k2y[k] then ky:=wy+s1
else ky:=wy-s1;
end;
c:=kx;
c:=ky;
exit;
end;
end;
procedure work;
begin
readln(n,vp,bg,ed);
if bg=ed then begin
writeln('0.00');
halt;
end;
fillchar(a,sizeof(a),255);
fillchar(c,sizeof(c),0);
fillchar(vis,sizeof(vis),false);
for i:=1 to n do begin
readln(x[1],y[1],x[2],y[2],x[3],y[3],t[i]);
for j:=1 to 4 do
d:=i;
change;
end;
n:=n*4;
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if d[i]=d[j] then
x1:=t[(i-1) div 4+1]
else x1:=vp;
l1:=sqrt(sqr(c-c[j,1])+sqr(c-c[j,2]));
a:=x1*l1;
a[j,i]:=a;
end;
vis[bg*4-1]:=true;
vis[bg*4-2]:=true;
vis[bg*4-3]:=true;
vis[bg*4]:=true;
for i:=1 to n do begin
min1:=10000000;
for l:=0 to 3 do
for j:=1 to n do
if not vis[j] then
if (a[bg*4-l,j]a[er,k]+a[k,j]
then a[er,j]:=a[er,k]+a[k,j];
end;
end;
begin
work;
end.
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| -
0
SecretAgent LV 10 @ 2009-08-26 14:18:33
预处理一下，然后Dijkstra
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
jiaoyunhao
LV 10
@ 2012-08-08 21:40:22
