Cod sursa(job #16388)

Utilizator andrei_infoMirestean Andrei andrei_info Data 12 februarie 2007 22:12:42
Problema Triang Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.99 kb
const aa = (sqrt(5)-1)/2;
      nmax = 1500;
      hashmax = 1000;

type    pc = record
                x,y:real;
                end;
        pnod = ^tnod;
        tnod = record
                x:pc;
                next:pnod;
                end;
        lista =record
                head,last:pnod;
                end;

var a :array[1..nmax]  of pc;
    pcc : array[0..hashmax] of lista;
    n:integer;

function hash(x:real):integer;
begin
hash:= abs(trunc(hashmax * ( frac(x*aa) )));
end;

function egal(x,y:real):boolean;
begin
if abs(x-y) < 0.0001 then egal:=true
else egal:=false;
end;

procedure inserthash(z:pc);
var poz,i:integer;
    p:pnod;
begin
poz:=hash(z.x+z.y);
new(p); p^.x:=z; p^.next:=nil;
if pcc[poz].head = nil then
        pcc[poz].head:=p
else    pcc[poz].last^.next:=p;
pcc[poz].last:=p;
end;

function cautahash(z:pc):boolean;
var p:pnod;
    poz:integer;
begin
cautahash:=false;
poz:=hash(z.x+z.y);
p:=pcc[poz].head;
while p <> nil do
        begin
        if egal(p^.x.x, z.x) and egal(p^.x.y, z.y) then
                cautahash:=true;
        p:=p^.next;
        end;

end;

procedure citire;
var i:integer;
begin
assign(input,'triang.in'); reset(input);
readln(n);
for i:=1 to n do
        begin
        readln(a[i].x,a[i].y);
        inserthash(a[i]);
        end;
closE(input);
end;

function panta(p1,p2:pc):double;
begin
panta:=- (p1.x-p2.x) / (p1.y-p2.y);
end;

function lungime(p1,p2:pc):double;
begin
lungime:=sqrt( sqr(p1.x-p2.x) + sqr(p1.y-p2.y) ) * sqrt(3) / 2;
end;

procedure calc;
var i,j:integer;
        rez:longint;
        ldd,mdd,xm,ym,xx1,xx2,yy1,yy2,r:real;
        p1,p2:pc;
begin
rez:=0;

for i:=1 to n-1 do
        for j:=i+1 to n do
                begin
                if  abs(a[i].y-a[j].y) > 0.0001 then
                        begin
                ldd:=lungime(a[i],a[j]);
                mdd:=panta(a[i],a[j]);
                xm:=(a[i].x+a[j].x) / 2;
                ym:=(a[i].y+a[j].y) / 2;
                xx1 := xm + sqrt( sqr(ldd) / (1+ sqr(mdd)));
                xx2 := xm - sqrt( sqr(ldd) / (1+ sqr(mdd)));
                r:=mdd*(xx1-xm);
                //writeln(r:5:10);
                //writeln(ym:5:10);
                //writeln(r+ym:5:10);
                yy1:= ym + r;
                yy2:= ym + mdd*(xx2-xm);
                        end
                else
                        begin
                        xm:=(a[i].x+a[j].x) /2 ;
                        ldd:=lungime(a[i],a[j]);
                        xx1:=xm; xx2:=xm;
                        yy1:=a[i].y+ldd;
                        yy2:=a[i].y-ldd;
                        end;
                p1.x:=xx1; p1.y:=yy1;
                p2.x:=xx2; p2.y:=yy2;
                if cautahash(p1) then inc(rez);
                if cautahash(p2) then inc(rez);
                end;
assign(output,'triang.out'); rewrite(output);
writeln(rez div 3);
close(output);
end;

begin
citire;
calc;
end.