题目:

题目描述

FJ想使用购买的新监控系统监视他的N头奶牛(1 <=N<= 50,000)。

第i头牛位置在(x_i, y_i),这是一对整数坐标,范围在0…1,000,000,000之内。FJ的监控系统有3个特殊的镜头,每一个镜头能够观察垂直或者水平的一行。

请决定FJ是否有可能架设这3个镜头,使他能够观察到所有的N头牛。也就是说,请决定N头牛的位置是否能同时被3条直线所覆盖。这3条直线必须是垂直或者水平的。

输入

第1行:1个整数N

第2..N+1行:2个整数x_i和y_i,表示第i头牛的坐标

输出

第1行:如果能监控所有的N头牛,则输出1,否则输出0

样例输入

6

1 7

0 0

1 2

2 0

1 4

3 4

样例输出

1

作者思路:dep表示第dep只奶牛,ans用来表示直线条数。
如果第i只奶牛已覆盖则不要把ans+1,否则+1。

代码:

var l1,l2,n:longint;
    x,y:array[0..50001] of longint;
    c:array[1..2,1..3] of longint;
procedure init;
var i:longint;
begin
  assign(input,'3lines.in');
  assign(output,'3lines.out');
  reset(input);
  rewrite(output);
  readln(n);
  for i:=1 to n do readln(x[i],y[i]);
end;
procedure dfs(dep,s:longint);
var i:longint;
    b:boolean;
begin
  if s>n then
  begin
    write(1);
    halt;
  end;
  b:=true;
  for i:=1 to l1 do if x[s]=c[1,i] then b:=false;
  for i:=1 to l2 do if y[s]=c[2,i] then b:=false;
  if (dep=3) and b then exit;
  if b then
  begin
    inc(l1);
    c[1,l1]:=x[s];
    dfs(dep+1,s+1);
    dec(l1);
    inc(l2);
    c[2,l2]:=y[s];
    dfs(dep+1,s+1);
    dec(l2);
  end else dfs(dep,s+1);
end;
begin
  init;
  dfs(0,1);
  write(0);
  close(input);
  close(output);
end.
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.