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 |
我的PAS文件(上面那个作废)In Reply To:我程序出错的原因是忘了给HASH表赋值 Posted by:cqf at 2006-03-28 11:21:52 program p2776(input,output); const maxh=4141; zero=1e-8; var hx,hy:array[0..maxh] of real; z:array[0..maxh] of longint; x,y,r,l:array[1..1000] of real; t,u,list:array[1..1000] of longint; lx,ly:array[1..2] of real; where,ans,all,i,j,k,len,m,n:longint; function touch(a,b:longint):longint; var cosa,sina,abx,aby,d:real; len:byte; procedure add(newx,newy:real); begin if (newx>=l[a])and(newx>=l[b]) then begin inc(len); lx[len]:=newx; ly[len]:=newy; end; end; begin d:=sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b])); if (d>r[a]+r[b]+zero)or(d<abs(r[a]-r[b])-zero) then exit(0); len:=0; if abs(d-r[a]-r[b])<=zero then add((x[a]*r[b]+x[b]*r[a])/(r[a]+r[b]),(y[a]*r[b]+y[b]*r[a])/(r[a]+r[b])) else if abs(d-abs(r[a]-r[b]))<=zero then if r[a]<r[b] then add((x[a]*r[b]-x[b]*r[a])/d,(y[a]*r[b]-y[b]*r[a])/d) else add((x[b]*r[a]-x[a]*r[b])/d,(y[b]*r[a]-y[a]*r[b])/d) else begin cosa:=(sqr(r[a])+sqr(d)-sqr(r[b]))/(2*r[a]*d); sina:=sqrt(1-sqr(cosa)); abx:=x[b]-x[a]; aby:=y[b]-y[a]; add((abx*cosa-aby*sina)*r[a]/d+x[a],(abx*sina+aby*cosa)*r[a]/d+y[a]); add((abx*cosa+aby*sina)*r[a]/d+x[a],(-abx*sina+aby*cosa)*r[a]/d+y[a]); end; touch:=len; end; procedure dfs(r:longint); var i:longint; begin u[r]:=1; inc(len); list[len]:=r; for i:=1 to n do if (u[i]=0)and(touch(r,i)>0)then dfs(i); end; function hash(a,b:real):longint; var i:longint; begin i:=abs(round(a*17+b*9891+17639))mod maxh; while (z[i]>0)and((abs(a-hx[i])>zero)or(abs(b-hy[i])>zero)) do i:=(i+1)mod maxh; hash:=i; end; begin readln(i); n:=0; for i:=1 to i do begin inc(n); readln(x[n],y[n],r[n],t[n]); for j:=1 to n-1 do if abs(x[n]-x[j])+abs(y[n]-y[j])+abs(r[n]-r[j])<zero then begin if t[j]<t[n] then t[j]:=t[n]; dec(n); break; end; end; for i:=1 to n do case t[i] of 1:l[i]:=x[i]+r[i]/sqrt(2)-zero; 2:l[i]:=x[i]-zero; 3:l[i]:=x[i]-r[i]/sqrt(2)-zero; 4:l[i]:=x[i]-r[i]-zero; end; fillchar(u,sizeof(u),0); ans:=1; for i:=1 to n do if u[i]=0 then begin len:=0; dfs(i); inc(ans); for j:=1 to len do begin all:=0; fillchar(z,sizeof(z),0); for k:=1 to j-1 do for m:=1 to touch(list[j],list[k]) do begin where:=hash(lx[m],ly[m]); if z[where]=0 then begin inc(all); hx[where]:=lx[m]; hy[where]:=ly[m]; end; inc(z[where]); end; if t[list[j]]<4 then inc(ans,all-1) else inc(ans,all); end; end; writeln(ans); end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator