|
|
題目鏈接：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;
}
|