[문제 풀이 보고서] hdu 1255 라인 트 리 + 스캐닝 라인

이 문 제 는 POJ 151 에 이 어 풀 렸 다. 이 문제 와 Atlantis 의 유일한 차이 점 은 이 문제 가 두 번 덮 는 면적 을 구 하 는 것 이다.방금 스캐닝 라인 을 배 웠 기 때문에 원래 의 템 플 릿 에서 어떻게 수정 해서 이 문 제 를 풀 수 있 을 까 생각 했다.제 생각 은 스 캔 라인 의 실제 길 이 를 구 할 때 커버 횟수 c > 0 을 판단 하면 이번 에는 c > 1 로 바 꾸 면 된다 는 것 입 니 다.그러나 실제 작업 에서 약간의 어려움 을 겪 었 다. 원래 계산 할 때 선분 1 의 y 가 1 에서 5 까지 라면 나 는 선분 트 리 에 가입 할 때 가장 큰 구간 으로 만 업데이트 되 고 하위 구간 까지 만 업데이트 되 지 않 기 때문이다.그러나 두 번 덮 인 길 이 를 계산 하려 면 구간 마다 업데이트 해 야 한다.원래 의 템 플 릿 구 조 를 바 꾸 지 않 는 상황 에서 제 방법 은 현재 변 경 된 상 태 를 기록 하고 노드 의 길 이 를 계산 할 때 아래로 전달 하 는 것 입 니 다 (약간의 lazy 맛 이 있 습 니 다. 안 타 깝 게 도 이것 은 매번 hhhh 를 전달 해 야 합 니 다). 그리고 하위 노드 를 업데이트 합 니 다.
PS: 제 가 인터넷 의 문 제 를 찾 아 봤 는데 모두 하나의 변 수 를 추가 하여 현재 구간 을 두 번 덮어 쓰 는 길 이 를 저장 합 니 다. 그들의 문 제 를 푸 는 방법 은 제 방법 보다 더 좋 을 수 있 습 니 다.그래도 자기가 생각 한 방법 이 니까 233 기념 으로 붙 여 주세요. 한 문제 에 여러 가지 AC 방법 이 있 잖 아 요.

#include 
#include 
#include 
using namespace std;
#define maxn 3001
double y[maxn];
struct node {
	int l, r, c;int lazy;
	double ly, ry, sum;
}tre[maxn << 3];
struct line {
	int  f;
	double x, y1, y2;
}l[maxn];//   1，  -1
bool cmp(line x, line y)
{
	return x.x < y.x;
}
void push_down(int n)
{
	tre[n].c += tre[n].lazy;
	if (tre[n].l + 1 != tre[n].r)
	{
		tre[n << 1 | 1].lazy += tre[n].lazy; tre[n << 1].lazy += tre[n].lazy;
	}
	tre[n].lazy = 0;
}
void build(int n, int l, int r)
{
	tre[n].l = l;tre[n].r = r;
	tre[n].c = tre[n].lazy = 0;;tre[n].sum = 0;
	tre[n].ly = y[l];tre[n].ry = y[r];
	if (l + 1 == r)
		return;
	int mid = (l + r) >> 1;
	build(n << 1, l, mid);
	build(n << 1 | 1, mid, r);//     [1,2][2,3],   mid
}
void calc(int n)
{
	push_down(n);
	if (tre[n].c > 1)
		tre[n].sum = tre[n].ry - tre[n].ly;
	else if (tre[n].l + 1 == tre[n].r)
		tre[n].sum = 0;
	else
	{
		calc(n << 1), calc(n << 1 | 1);
		tre[n].sum = tre[n << 1].sum + tre[n << 1 | 1].sum;
	}
}
void update(int n, line e)
{
	if (tre[n].ly == e.y1&&tre[n].ry == e.y2)//       
		tre[n].lazy += e.f;
	else if (e.y2 <= tre[n << 1].ry)update(n << 1, e);
	else if (e.y1 >= tre[n << 1 | 1].ly)update(n << 1 | 1, e);
	else
	{
		line t = e;
		t.y2 = tre[n << 1].ry;
		update(n << 1, t);
		t = e;
		t.y1 = tre[n << 1 | 1].ly;
		update(n << 1 | 1, t);
	}
	calc(n);
}
int main()
{
	int n,m, q = 1, t = 1;double ans;
	double x1, y1, x2, y2;
	scanf("%d", &m);
	while (m--)
	{
		scanf("%d", &n);
		ans = 0, t = 1;
		for (int i = 1;i <= n;i++)
		{
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			l[t].x = x1;
			l[t].y1 = y1;
			l[t].y2 = y2;
			l[t].f = 1;
			y[t++] = y1;
			l[t].x = x2;
			l[t].y1 = y1;
			l[t].y2 = y2;
			l[t].f = -1;
			y[t++] = y2;
		}
		sort(l + 1, l + t, cmp);
		sort(y + 1, y + t);
		build(1, 1, t - 1);//t-1   
		update(1, l[1]);//          
		for (int i = 2;i < t;i++)
		{
			ans += tre[1].sum*(l[i].x - l[i - 1].x);//   
			update(1, l[i]);//    i  
		}
		printf("%.2lf
", ans);
	}
	return 0;
}