记录编号	5249	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	[死·]丶Moon	是否通过	通过
代码语言	Pascal	运行时间	2.317 s
提交时间	2008-10-25 21:01:36	内存使用	3.65 MiB

type
  re=record
    x,y,t:longint;
  end;

var
  n,i,j,k,l:longint;
  star:array[1..50000] of re;
  final:array[-1..301,-1..301] of boolean;
  can:array[1..2,-1..1001,-1..1001] of boolean;
  cant:array[-1..1001,-1..1001] of boolean;

procedure sort(l,r:longint);
var
  i,j,x:longint;
  y:re;
begin
  i:=l;
  j:=r;
  x:=star[(l+r) div 2].t;
  repeat
    while star[i].t<x do inc(i);
    while x<star[j].t do dec(j);
    if not(i>j) then
    begin
      y:=star[i];
      star[i]:=star[j];
      star[j]:=y;
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

begin
  assign(input,'meteor.in');
  reset(input);
  assign(output,'meteor.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
  begin
    readln(star[i].x,star[i].y,star[i].t);
    final[star[i].x,star[i].y]:=true;
    final[star[i].x-1,star[i].y]:=true;
    final[star[i].x+1,star[i].y]:=true;
    final[star[i].x,star[i].y-1]:=true;
    final[star[i].x,star[i].y+1]:=true;
  end;
  final[-1,-1]:=true;
  can[1,0,0]:=true;
  sort(1,n);
  k:=1;
  for i:=0 to star[n].t do
  begin
    while (star[k].t<=i) and (k<=n) do
    begin
      cant[star[k].x,star[k].y]:=true;
      cant[star[k].x-1,star[k].y]:=true;
      cant[star[k].x+1,star[k].y]:=true;
      cant[star[k].x,star[k].y-1]:=true;
      cant[star[k].x,star[k].y+1]:=true;
      inc(k);
    end;
    for j:=0 to i do
      for l:=0 to i do
      begin
        if j+l>i then break;
        if not(cant[j,l]) then
          if can[1,j-1,l] or can[1,j+1,l] or can[1,j,l-1] or can[1,j,l+1] or can[1,j,l] then
          begin
            if not(final[j,l]) then
            begin
              writeln(i);
              close(input);
              close(output);
              halt;
            end;
            can[2,j,l]:=true;
          end
          else can[2,j,l]:=false;
      end;
    can[1]:=can[2];
  end;
  writeln(-1);
  close(input);
  close(output);
end.