| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么WA!!!program pku2653;
type xd=record
x1,y1,x2,y2:double;
end;
zx=record
k,b:double;
end;
dot=record
x,y:double;
end;
var n,t,i,j:longint;
a:array[0..100000]of xd;
b:array[0..100000]of longint;
p:xd;
function fc(a,b:dot):zx;
begin
if a.x=b.x then
begin
fc.k:=1e10;
fc.b:=a.x;
end
else
begin
fc.k:=(a.y-b.y)/(a.x-b.x);
fc.b:=a.y-a.x*fc.k;
end;
end;
function jd(l1,l2:zx):dot;
begin
if l1.k=1e10 then exit(jd(l2,l1));
if l2.k=1e10 then
begin
jd.x:=l2.b;
jd.y:=l1.k*jd.x+l1.b;
exit;
end;
jd.x:=(l2.b-l1.b)/(l1.k-l2.k);
jd.y:=l1.k*jd.x+l1.b;
end;
function zai(d:dot;x:xd):boolean;
begin
zai:=((d.x<=x.x1)and(d.x>=x.x2))or((d.x>=x.x1)and(d.x<=x.x2));
zai:=zai and((d.y<=x.y1)and(d.y>=x.y2))or((d.y>=x.y1)and(d.y<=x.y2));
if(d.x=x.x1)and(d.y=x.y1)then exit(false);
if(d.x=x.x2)and(d.y=x.y2)then exit(false);
end;
procedure swap(var x,y:double);
var t:double;
begin
t:=x;
x:=y;
y:=t;
end;
function xj(x,y:xd):boolean;
var d1,d2,d3,d4,d5:dot;
x1,x2:zx;
begin
d1.x:=x.x1;
d1.y:=x.y1;
d2.x:=x.x2;
d2.y:=x.y2;
d3.x:=y.x1;
d3.y:=y.y1;
d4.x:=y.x2;
d4.y:=y.y2;
x1:=fc(d1,d2);
x2:=fc(d3,d4);
if x1.k=x2.k then
begin
if x1.b<>x2.b then exit(false);
if x1.k<1e10 then
begin
if d1.x>d2.x then swap(d1.x,d2.x);
if d3.x>d4.x then swap(d3.x,d4.x);
if d1.x>d3.x then
begin
swap(d1.x,d3.x);
swap(d2.x,d4.x);
end;
if(d1.x<=d2.x)and(d2.x<=d3.x)and(d4.x>=d3.x)then exit(false)
else exit(true);
end
else
begin
if d1.y>d2.y then swap(d1.y,d2.y);
if d3.y>d4.y then swap(d3.y,d4.y);
if d1.y>d3.y then
begin
swap(d1.y,d3.y);
swap(d2.y,d4.y);
end;
if(d1.y<=d2.y)and(d2.y<=d3.y)and(d4.y>=d3.y)then exit(false)
else exit(true);
end;
end;
d5:=jd(x1,x2);
xj:=zai(d5,x)and(zai(d5,y));
end;
begin
repeat
readln(n);
if n=0 then halt;
t:=0;
for i:=1 to n do
begin
readln(p.x1,p.y1,p.x2,p.y2);
for j:=t downto 1 do
if xj(a[j],p)then
begin
a[j]:=a[t];
b[j]:=b[t];
dec(t);
end;
inc(t);
a[t]:=p;
b[t]:=i;
end;
write('Top sticks:');
for i:=1 to t-1 do write(' ',b[i],',');
writeln(' ',b[t],'.');
until 0=1;
end.
试了n组数据都是对的
难道有什么陷阱?
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator