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

---恢复内容开始---
题意：同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 扫描线+线段树面积并

最新文章

热门文章
