三条线 (Standard IO)

题意/Description:

       为了监视他的N (1 <= N <= 50,000)头奶牛，Farmer John购买了新的监视系统。第i头奶牛位置在(x_i, y_i)，坐标为整数，范围0..1,000,000,000。任意两头奶牛的位置不同。 
       FJ的监视系统有三个摄像头，每个摄像头只能监视一条水平线或者垂直线上的所有奶牛。请计算如果FJ安装好这三个摄像头，能否监视所有的N头奶牛。也就是说，计算N头奶牛的位置，是否可以被三条直线“覆盖”，直线必须是水平线或垂直线。

 

读入/Input：

       第1行：一个整数N。 
       第2..N+1行：第i+1行包含空格隔开的整数x_i 和y_i，给定第i头奶牛的位置。

 

输出/Output：

       第1行：如果使用三个摄像头，能监视所有的N头奶牛，请输出1。否则，输出0。  

 

题解/solution：

       看完题目，我们很容易想到离散化。离散化后，暴力每一个点，可用hash表查找。

 

代码/Code：

type
  arr=record
    x,y:longint;
  end;
var
  n:longint;
  a,b:array [0..50001] of arr;
  hash:array [0..100001,1..2] of longint;
procedure qsort1(l,r:longint);
var
 i,j,m,t:longint;
begin
  i:=l; j:=r;
  m:=a[(l+r) div 2].x;
  repeat
    while a[i].x>m do inc(i);
    while a[j].x<m do dec(j);
    if i<=j then
      begin
        t:=a[i].x; a[i].x:=a[j].x; a[j].x:=t;
        t:=a[i].y; a[i].y:=a[j].y; a[j].y:=t;
        inc(i); dec(j);
    end;
  until i>j;
  if l<j then qsort1(l,j);
  if i<r then qsort1(i,r);
end;

procedure qsort2(l,r:longint);
var
 i,j,m,t:longint;
begin
  i:=l; j:=r;
  m:=b[(l+r) div 2].y;
  repeat
    while b[i].y>m do inc(i);
    while b[j].y<m do dec(j);
    if i<=j then
      begin
        t:=b[i].y; b[i].y:=b[j].y; b[j].y:=t;
        t:=b[i].x; b[i].x:=b[j].x; b[j].x:=t;
        inc(i); dec(j);
    end;
  until i>j;
  if l<j then qsort2(l,j);
  if i<r then qsort2(i,r);
end;

procedure init;
var
  i:longint;
begin
  fillchar(hash,sizeof(hash),255);
  readln(n);
  for i:=1 to n do
    readln(a[i].x,a[i].y);
  b:=a;
  qsort1(1,n);
  qsort2(1,n);
  a[n+1].x:=maxlongint; a[n+1].y:=a[n+1].x;
  b[n+1].x:=maxlongint; b[n+1].y:=b[n+1].x;
end;

function try1(x,k:longint;p:boolean):boolean;
var
  i:longint;
begin
  i:=x mod 100000;
  while true do
    begin
      if hash[i,k]=x then exit(true);
      if hash[i,k]=-1 then
        begin
          if p then hash[i,k]:=x;
          exit(false);
        end;
      i:=(i+1) mod 100000;
    end;
end;

procedure main;
var
  i,k,cnt,kkk,kk,maxx:longint;
begin
  for k:=1 to 3 do
    begin
      cnt:=0; maxx:=0; kk:=0; kkk:=0;
      for i:=1 to n do
        if not try1(a[i].x,1,false) then
          begin
            if a[i].x=a[i+1].x then inc(cnt) else
              begin
                inc(cnt);
                if cnt>maxx then
                  begin
                    maxx:=cnt;
                    kkk:=a[i].x;
                    kk:=1;
                  end;
                cnt:=0;
              end;
          end;
      for i:=1 to n do
        if not try1(b[i].y,2,false) then
          begin
            if b[i].y=b[i+1].y then inc(cnt) else
              begin
                inc(cnt);
                if cnt>maxx then
                  begin
                    maxx:=cnt;
                    kkk:=b[i].y;
                    kk:=2;
                  end;
                cnt:=0;
              end;
          end;
      try1(kkk,kk,true);
    end;
end;

procedure print;
var
  i:longint;
  f:boolean;
begin
  f:=true;
  for i:=1 to n do
    if not try1(a[i].x,1,false) and not try1(a[i].y,2,false) then
      begin
        f:=false;
        break;
      end;
  if f then write('1')
       else write('0');
end;

begin
  init;
  main;
  print;
end.