题目描述

平面上给定N个两两不同的整点，统计以给定的点为顶点，且直角边平行于坐标轴的直角三角形数。

输入

输入文件right.in第一行为一个整数N。
以下N行，每行给出一个点的坐标。

输出

输出文件名为right.out。输出一个整数表示统计结果。

思路

就是和当前点横坐标相同数*纵坐标相同数就是了
但是直接找会超时，所以我们要先压缩然后二分查找这个点的位置

var
  i,j,k,n,m,s,x,y,l,r:longint;
  a,d,e:array[1..100000,1..2] of longint;
  b,c,o:array[1..100000] of longint;

procedure qsort(l,r:longint);
var
  i,j,k,key,t:longint;
begin
  i:=l; j:=r;
  key:=o[(l+r) div 2];
  repeat
    while o[i]key do dec(j);
    if i<=j then
      begin
        t:=o[i];
        o[i]:=o[j];
        o[j]:=t;
        inc(i); dec(j);
      end;
  until i>j;
  if l(x:longint):longint;
var low,hig,mid:longint;
begin
  low:=1;hig:=l;
  mid:=(low+hig) div 2;
  while (d[mid,1]<>x) and (low<=hig) do
  begin
  if d[mid,1]>x then hig:=mid-1
    else low:=mid+1;
    mid:=(low+hig) div 2;
  end;
  if low>hig then mid:=0;
  xx:=d[mid,2];
end;

function cc(x:longint):longint;
var low,hig,mid:longint;
begin
  low:=1;hig:=r;
  mid:=(low+hig) div 2;
  while (e[mid,1]<>x) and (low<=hig) do
  begin
  if e[mid,1]>x then hig:=mid-1
    else low:=mid+1;
    mid:=(low+hig) div 2;
  end;
  if low>hig then mid:=0;
  cc:=e[mid,2];
end;

begin
  readln(n);
  for i:=1 to n do
    begin
      readln(a[i,1],a[i,2]);
      b[i]:=a[i,1];
      c[i]:=a[i,2];
    end;

  o:=b;
  qsort(1,n);
  b:=o;
  o:=c;
  qsort(1,n);
  c:=o;
  x:=1;
  j:=1;
  for i:=1 to n do
    begin
      if b[i]=b[i+1]
        then begin
               inc(x);
             end
        else begin
               d[j,1]:=b[i];
               d[j,2]:=x;
               inc(j);
               x:=1;
             end;
    end;
  if b[n]<>b[n-1] then begin d[j,1]:=b[n]; d[j,2]:=1; inc(j); end;
  l:=j-1;
  j:=1;
  x:=1;
  j:=1;
  for i:=1 to n do
    begin
      if c[i]=c[i+1]
        then begin
               inc(x);
             end
        else begin
               e[j,1]:=c[i];
               e[j,2]:=x;
               inc(j);
               x:=1;
             end;
    end;
  if c[n]<>c[n-1] then begin e[j,1]:=b[n]; e[j,2]:=1; inc(j); end;
  r:=j-1;
  j:=1;

  for i:=1 to n do
    begin
      s:=s+(xx(a[i,1])-1)*(cc(a[i,2])-1);
    end;
  writeln(s);
end.