Picture POJ - 1177（扫描线求面积并）

题意：求矩形并的面积。。

解析：

　　扫描线第一道题。。。。自下而上扫描的。。。

如果不懂什么是扫描线 戳我

 

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _
ios_base::sync_wity_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 201, INF = 0x7fffffff;
double X[maxn];
//记录x的坐标
struct node{
int l, r;
// 线段树的左右端点
int w;
// 记录边重叠的情况
double lx, rx, sum; //sum代表当前区间线段的长度，lx和rx为线段的真实端点

}Node[maxn*4];
struct edge{
double lxx, rxx, y; // 存储边的左右端点和y
int f;
//标记是下边还是上边 （下边为1 上边为-1）
}Edge[maxn];
int cmp(edge a, edge b)
{
return a.y < b.y;
// 按y从小到大排序
把线段的高度从低到高排序
}
void build(int k, int ll, int rr) //建树
{
Node[k].l = ll, Node[k].r = rr;
Node[k].sum = Node[k].w = 0;
Node[k].lx = X[ll];
Node[k].rx = X[rr];
if(ll + 1 == rr) return;
int m = (ll + rr) / 2;
build(k*2, ll, m);
build(k*2+1, m, rr);
}
void down(int k)
//计算长度
{
if(Node[k].w > 0)
{
Node[k].sum = Node[k].rx - Node[k].lx;
return;
}
if(Node[k].l + 1 == Node[k].r) Node[k].sum = 0;
else
{
Node[k].sum = Node[k*2].sum + Node[k*2+1].sum;
}
}
void update(int k, edge e)
// 更新
{
if(Node[k].lx == e.lxx && Node[k].rx == e.rxx)
{
Node[k].w += e.f;
down(k);
return;
}
if(e.rxx <= Node[k*2].rx) update(k*2, e);
else if(e.lxx >= Node[k*2+1].lx) update(k*2+1, e);
else
{
edge g = e;
g.rxx = Node[k*2].rx;
update(k*2, g);
g = e;
g.lxx = Node[k*2+1].lx;
update(k*2+1, g);
}
down(k);
}
int main()
{
int n, cnt, kase = 0;
while(~scanf("%d",&n) && n)
{
cnt = 0;
for(int i=0; i<n; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf",&x1, &y1, &x2, &y2);
Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y1, Edge[cnt].f = 1;
X[cnt] = x1;
Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y2, Edge[cnt].f = -1;
X[cnt] = x2;
}
sort(Edge+1, Edge+cnt+1, cmp);
sort(X+1, X+cnt+1);
build(1, 1, cnt);
double ret = 0;
for(int i=1; i<cnt; i++)
{
update(1, Edge[i]);
ret += (Edge[i+1].y - Edge[i].y) * Node[1].sum;
}
printf("Test case #%dnTotal explored area: %.2fnn",++kase,ret);
}
return 0;
}