Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的PAS文件(上面那个作废)

Posted by cqf at 2006-03-28 11:40:20 on Problem 2776
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator