比赛 |
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;
}