随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 2760 End of Windless Days

题目链接:http://poj.org/problem?id=2760
/*
题意:
    给出N(N <= 500)个不透明矩形和它的高度,矩形上方有一盏灯,
可以通过照射投影到地面上,不被矩形投影覆盖的就会照亮,问最后照
亮的区域的面积。

解法:
离散化+线段树

思路:
    如果我们知道每个矩形在地面的投影,那么这个问题就转变成了求
矩形面积并的问题了,那么现在来看如何求一个矩形在地面的投影,可
以这样想,这里问题简化了,矩形必定和地面平行,所以是平行投影,
只会缩放,不会有透视效果,投影到地面上的还是矩形,然后考虑一维
的情况,一条线段在的投影,这个很简单,只要利用三角形相似就可以
求出投影线段的两端坐标,同样,二维的情况也是类似,只需要xy两维
分别做投影,当然这里的地面不是无穷大的,投影的矩形必须要和地面
的边界求交,把所有的投影求出来后利用线段树将所有矩形的面积并求
出来,然后用地面面积去减,就是最后照亮区域的面积了。
*/


#include 
<iostream>
#include 
<cmath>
#include 
<algorithm>
using namespace std;

#define maxn 2010
#define eps 1e-6


typedef 
double Type;

struct point {
    Type x, y;
    Type Height;
    point() 
{
        Height 
= 0;
    }

    
void SCANF_POINT() {
        
int tx, ty;
        scanf(
"%d %d"&tx, &ty);
        x 
= tx; y = ty;
    }

    
void SCANF_HEIGHT() {
        
int tmp;
        scanf(
"%d"&tmp);
        Height 
= tmp;
    }

}
;
point Min, Max, Light;

struct VLine {
    Type x, y0, y1;
    
int val;
    VLine() 
{}
    VLine(Type _x, Type _y0, Type _y1, 
int _v) {
        x 
= _x;
        y0 
= _y0;
        y1 
= _y1;
        val 
= _v;
    }

}
Vl[maxn*2];
int VlSize;
Type tmp[maxn];
int all, tot;

bool cmp(VLine a, VLine b) {
    
return a.x < b.x;
}


struct Rect {
    point L, R;

    
void SCANF() {
        L.SCANF_POINT();
        R.SCANF_POINT();

        L.SCANF_HEIGHT();
        R.Height 
= GetHeight();
    }


    Type GetHeight() 
{
        
return L.Height;
    }


    
bool ProjectionProcess();
}
Rec[maxn];

Type MMin(Type a, Type b) 
{
    
return a < b ? a : b;
}


Type MMax(Type a, Type b) 
{
    
return a > b ? a : b;
}


Type ProjectionCalculate(Type mx, Type mh, Type ux, Type uh) 
{
    
return ux - uh * (ux - mx) / (uh - mh);
}


bool Rect::ProjectionProcess() {
    L.x 
= MMax( Min.x, ProjectionCalculate(L.x, L.Height, Light.x, Light.Height));
    R.x 
= MMin( Max.x, ProjectionCalculate(R.x, R.Height, Light.x, Light.Height));

    L.y 
= MMax( Min.y, ProjectionCalculate(L.y, L.Height, Light.y, Light.Height));
    R.y 
= MMin( Max.y, ProjectionCalculate(R.y, R.Height, Light.y, Light.Height));

    
if(fabs(L.x - R.x) < eps || fabs(L.y - R.y) < eps)
        
return false;

    
return (L.x < R.x) && (L.y < R.y);
}


int Binary(double v) {
    
int l = 1;
    
int r = tot;
    
while(l <= r) {
        
int m = (l + r) >> 1;
        
if(fabs(tmp[m] - v) < eps)
            
return m;

        
if(v > tmp[m]) {
            l 
= m + 1;
        }
else
            r 
= m - 1;
    }

}


struct Tree {
    
int l, r;
    
int root;
    Type ylen;
    
int nCover;

    
void Update();
}
T[maxn*5];

void Tree::Update() {
    
if(nCover) {
        ylen 
= tmp[r] - tmp[l];
    }
else {
        
if(l + 1 == r)
            ylen 
= 0;
        
else
            ylen 
= T[root<<1].ylen + T[root<<1|1].ylen;
    }

}


void Build(int p, int l, int r) {
    T[p].l 
= l;
    T[p].root 
= p;
    T[p].r 
= r;
    T[p].nCover 
= 0;
    T[p].ylen 
= 0;
    
if(l + 1 == r) {
        
return ;
    }

    
int mid = (l + r) >> 1;
    Build(p
<<1, l, mid);
    Build(p
<<1|1, mid, r);
}


void Insert(int p, int l, int r, int val) {
    
if(l >= T[p].r || r <= T[p].l)
        
return ;

    
if(l <= T[p].l && T[p].r <= r) {
        T[p].nCover 
+= val;
        T[p].Update();
        
return ;
    }

    Insert(p
<<1, l, r, val);
    Insert(p
<<1|1, l, r, val);
    T[p].Update();
}


int n;
int main() {
    
int i;
    
while(scanf("%d"&n) != EOF) {
        Min.SCANF_POINT();
        Max.SCANF_POINT();
        Light.SCANF_POINT();
        Light.SCANF_HEIGHT();

        VlSize 
= 0;
        all 
= 1;
        tot 
= 0;

        
for(i = 0; i < n; i++{
            Rec[i].SCANF();
            
if( Rec[i].ProjectionProcess() ) {
                Vl[ VlSize 
++ ] = VLine(Rec[i].L.x, Rec[i].L.y, Rec[i].R.y, 1);
                Vl[ VlSize 
++ ] = VLine(Rec[i].R.x, Rec[i].L.y, Rec[i].R.y, -1);

                tmp[all
++= Rec[i].L.y;
                tmp[all
++= Rec[i].R.y;
            }

        }

        sort(tmp 
+ 1, tmp + all + 1);
        sort(Vl, Vl 
+ VlSize, cmp);

        
for(i = 1; i <= all; i++{
            
if(i==1 || fabs(tmp[i] - tmp[i-1]) > eps) {
                tmp[
++tot] = tmp[i];
            }

        }

        
double ans = (Max.x-Min.x) * (Max.y-Min.y);
        
if(tot >= 2{
            Build(
11, tot);
            
for(i = 0; i < VlSize; i++{
                
if(i) {
                    ans 
-= (Vl[i].x - Vl[i-1].x) * T[1].ylen;
                }

                Insert(
1, Binary(Vl[i].y0), Binary(Vl[i].y1), Vl[i].val);
            }

        }


        printf(
"%.4lf\n", ans);
    }

    
return 0;
}

posted on 2011-04-03 12:50 英雄哪里出来 阅读(1107) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理