比赛 SYOI 专题 5:扫描线 评测结果 AAAAAAAAAA
题目名称 亚特兰蒂斯 最终得分 100
用户昵称 yuan 运行时间 1.556 s
代码语言 C++ 内存使用 6.66 MiB
提交时间 2024-04-23 17:10:42
显示代码纯文本
#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;
}