题解 P1302 【可见矩形】

· · 题解

(ggb大法好.).

题意,给出n个互不相交的正方形.求有多少个可见的正方形.

设原点(0,0)为O.

1个正方形是可见的条件为:

在正方形边上选取2个不同的点X,Y.存在1种方法使△OXY与其他正方形没有公共点.

可以看出.△OXY面积越小，与其他正方形的公共部分只减不增.

在X = Y时.面积为0.

由于X与Y不能相同,可以使X无限接近Y.

这个时候只要求线段OY与其他正方形有没有相交了.

怎么求相交.?

对于正方形T边上2点X,Y.在∠XOY内,△OXY外的正方形,边上任取点Z.OZ与T必然有交.

什么东西.?就是正方形被完全覆盖(不可见.).

(这不是废话吗线都是直的- -.)..

很显然,X,Y取到正方形左上右下端点,∠XOY最大.

结合之前"X无限接近Y".边正好不超过OX或者OY的正方形同样不可见.

(事实上就是只能看见1个点....不满足3角形.).

poi区域不可见.

如何判断是否在poi里.?

斜率.对于正方形上任意1点Z.OZ的斜率在OX与OY之间.

用k1_i,k2_i表示斜率区间.实际上只要判断区间是否完全被覆盖.

n<=1000. n²枚举即可..

不过.在△OXY内的正方形同样满足斜率.但他可见.

而且上面遗留了个问题.1些正方形的poi区间可以共同覆盖.

........

我试图通过优先级消除影响.先枚举离O"比较近"的点.

依照题意.△OXY内所有正方形必须先枚举到.

被这个正方形或者多个正方形弄得不可见的正方形必须在这之后枚举.

如何确定优先关键字.?

只用1个点很难受,到处反例.我是找不出来了...

接上图- -.并接1句废话- -.

点X左侧所有点横坐标<X的横坐标.点Y下侧所有点纵坐标<Y的纵坐标.

于是按输入点横纵坐标取min排序就好了.

最后才发现...这东西具有良好的传递性.相互之间不会干扰..

多亏了题目限制.真是令人开心..

排完序后1~n枚举.询问在前面所有区间共同覆盖后能否完全覆盖这个区间.

代码.请删掉注释食用.

program P1302;
 uses math,Garrayutils;
 const
  sqrnd=1008208820;
 type
  we=record
   x,y,z:longint;
  end;
  wa=array[0..1001] of we;
  wr=array[0..1001] of real;
  cmp=object
   public
   function c(x,y:we):boolean;inline;
  end;
  sort=specialize Torderingarrayutils<wa,we,cmp>;
 var
  x,y,z:wa;
  i,j,n,ssum:longint;
  p1,p2:real;
  k1,k2:wr;
 function cmp.c(x,y:we):boolean;inline;//比较.
  begin
   //exit(x.x+x.y<y.x+y.y);
   exit(min(sqrt(sqr(x.x+x.z)+sqr(x.y)),sqrt(sqr(x.x)+sqr(x.y+x.z)))<min(sqrt(sqr(y.y)+sqr(y.z+y.x)),sqrt(sqr(y.z+y.y)+sqr(y.x))));
  end;
 begin
  readln(n);
  for i:=0 to n-1 do
   readln(x[i].x,x[i].y,x[i].z);
  sort.sort(x,n);       //按奇怪的性质排序.
  ssum:=0;
  p1:=1008208820;
  p2:=0;
  for i:=0 to n-1 do
   begin
    k1[i]:=x[i].y/(x[i].x+x[i].z);
    k2[i]:=(x[i].y+x[i].z)/x[i].x; //斜率区间.
    //if (k1<p1) or (k2>p2) then inc(ssum);
    //p1:=min(p1,k1);
    //p2:=max(p2,k2);
    p1:=k1[i];
    p2:=k2[i];
    for j:=0 to i-1 do  //通过排完序的区间判断覆盖.
     begin
      //if (k2[i]>k2[j]) or (k1[i]<k1[j]) then continue
      if k1[j]>p1 then break;
      p1:=max(p1,k2[j]);
     end;
    if p1<p2 then inc(ssum);
    p1:=k1[i];
    p2:=k2[i];
    for j:=i downto 0 do  //区间的插入排序.
     begin
      if j=0 then break;
      if p1>k1[j-1] then break;
      k1[j]:=k1[j-1];
      k2[j]:=k2[j-1];
     end;
    k1[j]:=p1;
    k2[j]:=p2;
   end;
  writeln(ssum);
 end.
来自攻略组团队中混饭人员的贡献.

(ಡωಡ).