---恢复内容开始---

LINK

题意：同POJ1151

思路：

/** @Date    : 2017-07-19 13:24:45  * @FileName: POJ 1389 线段树+扫描线+面积并 同1151.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;struct yuu{	int l, r;	int flag;	int ll, rr;	int len;}tt[N];struct line{	int y, x1, x2;	int flag;	line(){}	line(int _x1, int _x2, int _y, int f){		x1 = _x1;		x2 = _x2;		y = _y;		flag = f;	}};line li[N];int cmp(line a, line b){	return a.y < b.y;}double a[N], b[N];void pushup(int p){	if(tt[p].flag > 0)	{		tt[p].len = tt[p].rr - tt[p].ll;		return ;	}	if(tt[p].l == tt[p].r - 1)		tt[p].len = 0;	else 		tt[p].len = tt[p << 1].len + tt[p << 1 | 1].len;}void build(int l, int r, int p){	tt[p].l = l;	tt[p].r = r;	tt[p].len = tt[p].flag = 0;	tt[p].ll = a[l];	tt[p].rr = a[r];	if(l == r - 1)		return ;	int mid = (l + r) >> 1;	build(l, mid, p << 1);	build(mid, r, p << 1 | 1);}void update(int x1, int x2, int flag, int p){	if(x1 == tt[p].ll && x2 == tt[p].rr)	{		tt[p].flag += flag;		pushup(p);		return ;	}	if(x2 <= tt[p << 1].rr)		update(x1, x2, flag, p << 1);	else if(x1 >= tt[p << 1 | 1].ll)		update(x1, x2, flag, p << 1 | 1);	else	{		update(x1, tt[p << 1].rr, flag, p << 1);		update(tt[p << 1 | 1].ll, x2, flag, p << 1 | 1);	}	pushup(p);}int main(){		int x1, x2, y1, y2;		while(~scanf("%d%d%d%d", &x1, &y1, &x2, &y2) && ( (~x1) || (~x2) || (~y1) || (~y2)))		{			int cnt = 1;			li[cnt] = line(x1, x2, y1, 1);			a[cnt++] = x1;			li[cnt] = line(x1, x2, y2, -1);			a[cnt++] = x2;			while(scanf("%d%d%d%d", &x1, &y1, &x2, &y2) && (((~x1)||(~x2)||(~y1)||(~y2))))			{				li[cnt] = line(x1, x2, y1, 1);				a[cnt++] = x1;				li[cnt] = line(x1, x2, y2, -1);				a[cnt++] = x2;			}			sort(li + 1, li + cnt, cmp);			sort(a + 1, a + cnt);			build(1, cnt - 1, 1);			update(li[1].x1, li[1].x2, li[1].flag, 1);			int ans = 0;			for(int i = 2; i < cnt; i++)			{				//cout << li[i].x1 << "#" << li[i].x2 << "#" << li[i].y << endl;				ans += tt[1].len * (li[i].y - li[i - 1].y);				update(li[i].x1, li[i].x2, li[i].flag, 1);				//cout << "~";			}			printf("%d\n", ans);					}    return 0;}

---恢复内容结束---

POJ 1389 Area of Simple Polygons 扫描线+线段树面积并