直角三角形_紀中2543_暴力?

NO IMAGE

Description

  平面上給定N個兩兩不同的整點,統計以給定的點為頂點,且直角邊平行於座標軸的直角三角形數。

Input

  輸入檔案right.in第一行為一個整數N。
  以下N行,每行給出一個點的座標。

Output

  輸出檔名為right.out。輸出一個整數表示統計結果。

Hint

[資料規模和約定]

  30%的資料滿足 N ≤ 100;
  50%的資料滿足 N ≤ 1000;
  100%的資料滿足0 < N ≤ 100000,所有座標不超過32位整數範圍。
  

題意

求互相垂直並平行於座標軸的線段對數

題解

跟之前做過一題很像,但是有限制條件
用陣列記錄縱座標和橫座標上的點的線段數量,空間優化用雜湊表,離散似乎不是必要但是也打了
列舉點統計以此為直角頂點的三角形數量
c 神坑陣列不能為負數於是換回了fp

code

const
p=403219;
var
n:longint;
hx,hy,vx,vy,x,y,s,t:array[-p..p]of longint;
function hash_x(x:longint):longint;
var
i:longint;
begin
i:=(x)mod p;
while (hx[i]<>0)and(hx[i]<>x) do
i:=(i 1)mod p;
exit(i);
end;
function hash_y(y:longint):longint;
var
i:longint;
begin
i:=(y)mod p;
while (hy[i]<>0)and(hy[i]<>y) do
i:=(i 1)mod p;
exit(i);
end;
procedure init;
var
i,g,ans,a,b:longint;
begin
a:=0;
b:=0;
ans:=0;
readln(n);
for i:=1 to n do
begin
readln(x[i],y[i]);
g:=hash_x(x[i]);
if (hx[g]<>x[i]) then
begin
inc(a);
hx[g]:=x[i];
s[g]:=a;
inc(vx[s[g]]);
end
else
inc(vx[s[g]]);
g:=hash_y(y[i]);
if (hy[g]<>y[i]) then
begin
inc(b);
hy[g]:=y[i];
t[g]:=b;
inc(vy[t[g]]);
end
else
inc(vy[t[g]]);
end;
for i:=1 to n do
begin
ans:=ans (vx[s[hash_x(x[i])]]-1)*(vy[t[hash_y(y[i])]]-1);
end;
writeln(ans);
end;
begin
init;
end.