|
题目链接: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(1, 1, 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; }
|