题解 P2202 【[USACO13JAN]方块重叠Square Overlap】

scarborough_fair · 2017-11-04 10:47:57 · 题解

来一发Pascal题解（吐槽一下难度确实不合理）

本题主要考察得是线（暴）性（力）扫（枚）描（举）（>_>）的思想

对于N个正方形，可以知道当正方形A、B的坐标为（x1,y1）(x2,y2)时，abs（x1-x2）<k 且abs（y1-y2）<k正方形会出现重叠

对于50000个正方形，枚举显然是可以过的，于是上代码

var i,j,k,l,n,num,ans,r:longint;
    x,y:array[1..500000] of longint;
procedure sort(l,r:longint);
var i,j,t,m:longint;
begin
  i:=l;j:=r;m:=x[(i+j) div 2];
  repeat
    while x[i]<m do inc(i);
    while x[j]>m do dec(j);
    if not(i>j) then begin
      t:=x[i];x[i]:=x[j];x[j]:=t;
      t:=y[i];y[i]:=y[j];y[j]:=t;
      inc(i);dec(j);end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;
begin
  readln(n,k);
  for i:=1 to n do read(x[i],y[i]);
  sort(1,n);//按坐标排序，便于枚举
  ans:=0;
  for l:=1 to n-1 do
   begin
     r:=l+1;   num:=0;//按1到n-1枚举l个正方形，则判断R=l+1个正方形的坐标
     while (x[r]-x[l]<k)and(r<=n) do
       begin
         if (abs(y[r]-y[l])<k) then//如果有重叠，计算面积为ans
         if ans=0 then
           ans:=(k-abs(x[r]-x[l]))*(k-abs(y[r]-y[l]))
         else begin ans:=-1;   break;end;
         if ans=-1 then break;inc(r);//线性扫描的精髓，若当前的r满足与l重叠，则向右扩张，否则break跳出循环，l想做推进
        end;
     if ans=-1 then break;//如果完全无重叠则返回-1
  end;
  writeln(ans);
end.