摄影师的烦恼

原文链接：[url]http://www.mydrs.org/program/list.asp?id=158[/url]

【问题描述】

　　摄影师Tension在他的3D工作室里布置了一些布景（假设所有的布景都是正四棱柱，并且都直接放在地板上）。
　　为了描述这些布景的位置，我们在地板上建立了直角坐标系，原点O处是Tension和他的照相机。对于每一个正四棱柱的布景，用它的底面正方形的中心坐标(Ｘc，Ｙc)来标识它的位置，用底面边长d和棱柱的高h来标识它的形状（如图）。同时，每一布景的放置都是规则的，也就是说，所有棱柱底面的棱都平行于坐标轴。当然，任意两个布景（正四棱柱）是不可能有重叠的部分。
             [img]http://www.chinaschool.org/aosai/lwjl/images/s-1.gif[/img]
　　对于站在坐标原点O的Tension而言(Tension趴在地上，高度视为0)，一个四棱柱表面上的某个点，当且仅当它与原点的连线（也就是观察者的视线）不再穿过任何四棱柱的表面（包括棱和顶点）时，才被认为是可见的；如果一个四棱柱表面上存在可见的点，那么我们就认为这个四棱柱是可见的，这时，Tension就可以从照相机里看到这个布景（全部或者一部分）。

　　当Tensoin布置完这些布景之后，他想要了解从他所站的位置到底能够看到多少布景，但是当布景相当多的时候，这着实让Tension苦恼。而您的任务，就是利用程序求出在坐标原点O可见的四棱柱的个数m。
【输入输出】

　　输入文件visible.in的第一行是一个正整数N，表示正四棱柱的总数。
　　从第2行至第N+1行，每行各有4个正整数Ｘi，Ｙi，Ｄi，Ｈi，用空格分隔开，表示一个正四棱柱的中心坐标、底边长和高。
　　输出文件visible.out只有一个整数m，表示可见的正四棱柱的个数。
【数据说明】

　　所有四棱柱的底面顶点坐标（x，y）都满足：
　　0＜x≤65000，0＜y≤65000；（也就是说，所有坐标都在第一象限内）
　　对于四棱柱的形状的限制有 0＜d≤65000，0＜h≤65000；
　　布景的总数为N，且1≤N≤1000。
【评分说明】

　　只有完全正确的输出才能够获得测试点的分数。




作者：国家集训队
来源：冬令营试题

题目是这样的把

2001年国家集训队冬令营试题，怪不得这么难
我也不会~~ ：Ｐ

我来试试，判断依据是：底面区域areaB[]包括两条线分别为K1X-Y>=0和K2X-Y<=0;我们采用区域合并的方法把经过并能遮住T[I]正四棱柱的区域合并，得B1个区域。则如果T[I]会被其中的某个区域遮住T[I]不可见。而对于高度的处理则采用一开始判断：对于T[J]形成A[J]区域，如果A[J]投影（往空中投）到T[I]高度不够，则不考虑A[J]形成的区域。
程序按由远及近判断，所以用了个冒泡排序。。。。。。
程序分段发过来（你也可去我的BLOG看看：http://hi.baidu.com/649786031/blog）
我只用了几个数据测试通过了，不知道正不正确

program tension;
   type ss=record
         s,d,h,x,y:real;
             end;
   type area=record
         h,k1,k2:real;
             end;
   var t:array[1..1000]of ss;
       b,a:array[1..1000]of area;
       see:array[1..1000]of boolean;
     b1,a1,i,j,k,m,n,t1,l:integer;
        p,flag:boolean;
        x,y,d,h:real;

    procedure swap(var a,b:real);
         var t:real;
         begin
           t:=a;a:=b;b:=t;
           end;
     begin
      fillchar(see,sizeof(see),true);
      readln(n);
      for i:=1 to n do
        begin
         readln(x,y,d,h);
         t[i].x:=x;t[i].y:=y;t[i].d:=d;t[i].h:=h;
         t[i].s:=sqrt(x*x+y*y);
         a[i].h:=h;a[i].k1:=(2*y+d)/(2*x-d);a[i].k2:=(2*y-d)/(2*x+d);
         end;
      i:=1;
      repeat
          flag:=true;
          for j:=1 to n-i do
             if t[j].s<t[j+1].s then
               begin
                swap(t[j].s,t[j+1].s);
                swap(t[j].x,t[j+1].x);
                swap(t[j].y,t[j+1].y);
                swap(t[j].d,t[j+1].d);
                swap(t[j].h,t[j+1].h);
                swap(a[j].h,a[j+1].h);
                swap(a[j].k1,a[j+1].k1);
                swap(a[j].k2,a[j+1].k2);
                flag:=false;
                end;
           inc(i);
         until flag;

for i:=1 to n do
       begin
          b1:=0;
          for j:=i+1 to n do
            if (not(a[j].k1<a[i].k2))and(not(a[j].k2>a[i].k1))and(t[j].h>=(t[i].h*t[j].x/(t[j].x+t[i].x))) then
              begin
                flag:=true;
               for t1:=1 to b1 do
                if (a[j].k1>b[t1].k2)and(a[j].k1<b[t1].k1)and(a[j].k2<b[t1].k2) then
                 begin
                      flag:=false;
                      b[t1].k2:=a[j].k2;
                    end
             else if (a[j].k2>b[t1].k2)and(a[j].k2<b[t1].k1)and(a[j].k1>b[t1].k1)then
                 begin
                    flag:=false;
                    b[t1].k1:=a[j].k1;
                   end
             else if (a[j].k1<b[t1].k1)and(a[j].k2>b[t1].k2)then flag:=false
             else if (a[j].k1>b[t1].k1)and(a[j].k2<b[t1].k2)then begin
                                                                 flag:=false;
                                                                 b[t1].k1:=a[j].k1;
                                                                 b[t1].k2:=a[j].k2;
                                                                 end;
              if flag=true then begin
                   inc(b1);b[b1].k1:=a[j].k1;
                           b[b1].k2:=a[j].k2;
                                end;
               end;
            for t1:=1 to b1 do
              for l:=1 to b1 do
                if (b[l].k1>b[t1].k2)and(b[l].k2<b[t1].k2)then
                begin
                  b[t1].k2:=b[l].k2;
                  end
            else if (b[l].k2<b[t1].k1)and(b[l].k1>b[t1].k1) then
                begin
                  b[t1].k1:=b[l].k1;
                 end;
       for t1:=1 to b1 do
         if (a[i].k1<=b[t1].k1)and(a[i].k2>=b[t1].k2)then
            begin
              see[i]:=false;break;
             end;
       end;
    m:=0;
    for i:=1 to n do
      if see[i]=true then inc(m);
  writeln(m);
end.