比赛 SYOI 专题 5:扫描线 评测结果 RRRRRRRRRR
题目名称 HH的项链 最终得分 0
用户昵称 yuan 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2024-04-22 18:20:36
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10005;
double x[maxn<<1];//存x坐标,每个矩形存2个点
struct line
{//用结构体记录每一条线段
	double l, r, h;//左端点,右端点,y轴(高度)
	int d;//标记上下边,上边为-1,下边为1
} a[maxn<<1];//一个矩形对应上下两条边

struct Node
{
	int tl, tr;//区间边界
	int sum;//该区间被完全覆盖的次数
	double len;//该区间被覆盖的总长度
} tree[maxn<<3];//离散化后空间大概是(2*maxn)*4

void build(int u, int tl, int tr)
{//建树
	tree[u].tl=tl;
	tree[u].tr=tr;
	tree[u].sum=0;
	tree[u].len=0;
	if(tl==tr) return;
	int mid=(tl+tr)/2;
	build(u*2, tl, mid);
	build(u*2+1, mid+1, tr);
}

void pushup(int u)
{
	if(tree[u].sum)
	{//当前区间被完全覆盖
		tree[u].len=x[tree[u].tr]-x[tree[u].tl-1];//区间长度
	}
	else//该段不被完全覆盖,那么清空该段的len值,而由可能存在其子区间段对len的贡献来更新
		if(tree[u].tl==tree[u].tr)
		{//叶子结点
			tree[u].len=0;
		}
	else
	{//由孩子对len的贡献进行更新
		tree[u].len=tree[u*2].len+tree[u*2+1].len;
	}
}

void update(int u, int ql, int qr, int f)
{//插入新线段,该线段覆盖的区域覆盖次数 +f
	int tl=tree[u].tl;
	int tr=tree[u].tr;
	if(ql<=tl && tr<=qr)
	{//结点区间完全被包含在被修改区间内
		tree[u].sum += f;//累加完全覆盖次数
		pushup(u);
		return;
	}
	int mid=(tl+tr)/2;
	if(mid>=ql) update(u*2, ql, qr, f);
	if(mid< qr) update(u*2+1, ql, qr, f);
	pushup(u);
}

bool cmp(struct line X, struct line Y)
{
	return X.h<Y.h;
}

int main()
{
	freopen("atlantis.in","r",stdin);
	freopen("atlantis.out","w",stdout);
	int T, Case=0;
	while(~scanf("%d", &T)&&T)
	{
		int i, m=0;
		for(i=1; i<=T; i++)
		{
			double x1, y1, x2, y2;
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			if(y1>y2) swap(y1,y2);
			a[m].l=x1, a[m].r=x2, a[m].h=y1, a[m].d=1;
			x[m++]=x1;
			a[m].l=x1, a[m].r=x2, a[m].h=y2, a[m].d=-1;
			x[m++]=x2;
		}
		sort(x, x+m);//离散第1步:排序需离散的空间
		sort(a, a+m, cmp);//矩形按高度排序
		int len=unique(x, x+m)-x;//离散第2步:去重
		build(1, 1, len);
		double area=0.0;
		for(i=0; i<m; i++)//离散化各点,并更新线段树
		{
			//离散化第3步:索引元素离散化后对应的值
			//lower_bound()返回指向大于等于key的第一个值的位置指针
			int l=lower_bound(x,x+len,a[i].l)-x+1;
			int r=lower_bound(x,x+len,a[i].r)-x;
			//[左闭右开)性质,与普通的线段树记录点不同,这里记录的是线段
			update(1, l, r, a[i].d);
			area+=(a[i+1].h-a[i].h)*tree[1].len;
			//tree[1]是整个区间,tree[1].len是整个区间的有效长度
		}
		printf("Test case #%d\nTotal explored area: %.2f\n\n",++Case, area);
	}
	return 0;
}