🧠 题解（Solution）

✅ 本质问题

本题本质上是计算多个二维矩形区域的并集面积，这是一个典型的矩形并面积求解问题，可以用**扫描线算法（Sweep Line）**解决。

🔍 解题思路

将所有矩形分割为事件：

每个矩形会产生两个“事件”：左边界进入、右边界离开；

每个事件记录： x x 坐标、上下 y y 区间、类型（加入/删除）；

按 x x 坐标排序事件，依次处理；

每次处理当前 x x 和上一个 x x 之间的 d x dx；

同时维护当前 y y 轴上被覆盖的总长度 l e n len；

每次更新面积：

area + 𝑑 𝑥 ⋅ 𝑙 𝑒 𝑛 area+=dx⋅len 使用区间树或线段树/计数数组维护 y y 区间是否被覆盖；

为了处理浮点数，先将所有 y y 坐标离散化（映射为整数索引）；

每次事件更新后，重新计算当前 y y 总覆盖长度。

📌 示例说明（输入数据 1）：

两个矩形：

第一个： ( 10 , 10 ) − ( 20 , 20 ) (10,10)−(20,20)，面积 100 100；

第二个： ( 15 , 15 ) − ( 25 , 25.5 ) (15,15)−(25,25.5)，面积 105 105；

重叠区域： ( 15 , 15 ) − ( 20 , 20 ) (15,15)−(20,20)，面积 25 25；

并集面积： 100 + 105 − 25

180.00 100+105−25=180.00

✅ 算法复杂度

O ( n log ⁡ n ) O(nlogn)：用于事件排序；

O ( n log ⁡ m ) O(nlogm)：用于线段树维护 y y 区间（ m m 为离散后的 y y 坐标数）；

高效且适用于浮点输入。

正确代码

#include <iostream>
#include <memory>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=210;

int n,kase;
struct re{
	double x,y,y1;
	int is;
}rec[maxn];
bool cmp(const re &a,const re &b){return a.x<b.x;}
double d[maxn];int cnt;
inline int query(double x){return lower_bound(d+1,d+cnt+1,x)-d;}

struct node{
#define ls(x) t[x].lc
#define rs(x) t[x].rc
	int lc,rc,tag;
	double len;
}t[maxn<<1];
int tot,root;
inline void maintain(int o,int l,int r){
	if(t[o].tag>0)t[o].len=d[r+1]-d[l];
	else t[o].len=t[ls(o)].len+t[rs(o)].len;
}
void modify(int &o,int l,int r,int x,int y,int val){
	if(!o)o=++tot;
	if(l==x&&r==y){t[o].tag+=val;maintain(o,l,r);return;}
	int mid=l+r>>1;
	if(y<=mid)modify(ls(o),l,mid,x,y,val);
	else if(x>mid)modify(rs(o),mid+1,r,x,y,val);
	else modify(ls(o),l,mid,x,mid,val),modify(rs(o),mid+1,r,mid+1,y,val);
	maintain(o,l,r);
}

void read_and_parse(){
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf%lf",&rec[i].x,&rec[i].y,&rec[i+n].x,&rec[i+n].y);
		rec[i].y1=rec[i+n].y,rec[i+n].y1=rec[i].y;
		rec[i].is=0,rec[i+n].is=1;
		d[i]=rec[i].y,d[i+n]=rec[i+n].y;
	}
	sort(rec+1,rec+2*n+1,cmp);
	sort(d+1,d+2*n+1);
	cnt=unique(d+1,d+2*n+1)-d-1;
}

void solve(){
	double ans=0;
	for(int i=1;i<2*n;i++){
		int l=query(rec[i].y),r=query(rec[i].y1);
		if(!rec[i].is)modify(root,1,cnt-1,l,r-1,1);
		else modify(root,1,cnt-1,r,l-1,-1);
		ans+=(rec[i+1].x-rec[i].x)*t[root].len;
	}
	printf("Test case #%d\n",++kase);
	printf("Total explored area: %.2lf\n",ans);
	puts("");
}

int main(){
	while(scanf("%d",&n)&&n){
		memset(t,0,sizeof(t)),memset(rec,0,sizeof(rec));
		tot=root=0;
		read_and_parse();
		solve();    
	}
	return 0;
}

🧠 题解（Solution）

✅ 本质问题

本题本质上是计算多个二维矩形区域的并集面积，这是一个典型的矩形并面积求解问题，可以用**扫描线算法（Sweep Line）**解决。

🔍 解题思路

将所有矩形分割为事件：

每个矩形会产生两个“事件”：左边界进入、右边界离开；

每个事件记录：$x$ 坐标、上下 $y$ 区间、类型（加入/删除）；

按 $x$ 坐标排序事件，依次处理；

每次处理当前 $x$ 和上一个 $x$ 之间的 $dx$；

同时维护当前 $y$ 轴上被覆盖的总长度 $len$；

每次更新面积：

area +

𝑑 𝑥 ⋅ 𝑙 𝑒 𝑛 area+=dx⋅len 使用区间树或线段树/计数数组维护 $y$ 区间是否被覆盖；

为了处理浮点数，先将所有 $y$ 坐标离散化（映射为整数索引）；

每次事件更新后，重新计算当前 $y$ 总覆盖长度。

📌 示例说明（输入数据 1）：

两个矩形：

第一个：$(10,10)-(20,20)$，面积 $100$；

第二个：$(15,15)-(25,25.5)$，面积 $105$；

重叠区域：$(15,15)-(20,20)$，面积 $25$；

并集面积：$100 + 105 - 25 = 180.00$

✅ 算法复杂度

$O(n \log n)$：用于事件排序；

$O(n \log m)$：用于线段树维护 $y$ 区间（$m$ 为离散后的 $y$ 坐标数）；

高效且适用于浮点输入。

代码实现：

#include <iostream>
#include <memory>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=210;

int n,kase;
struct re{
    double x,y,y1;
    int is;
}rec[maxn];
bool cmp(const re &a,const re &b){return a.x<b.x;}
double d[maxn];int cnt;
inline int query(double x){return lower_bound(d+1,d+cnt+1,x)-d;}

struct node{
#define ls(x) t[x].lc
#define rs(x) t[x].rc
    int lc,rc,tag;
    double len;
}t[maxn<<1];
int tot,root;
inline void maintain(int o,int l,int r){
    if(t[o].tag>0)t[o].len=d[r+1]-d[l];
    else t[o].len=t[ls(o)].len+t[rs(o)].len;
}
void modify(int &o,int l,int r,int x,int y,int val){
    if(!o)o=++tot;
    if(l==x&&r==y){t[o].tag+=val;maintain(o,l,r);return;}
    int mid=l+r>>1;
    if(y<=mid)modify(ls(o),l,mid,x,y,val);
    else if(x>mid)modify(rs(o),mid+1,r,x,y,val);
    else modify(ls(o),l,mid,x,mid,val),modify(rs(o),mid+1,r,mid+1,y,val);
    maintain(o,l,r);
}

void read_and_parse(){
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf%lf",&rec[i].x,&rec[i].y,&rec[i+n].x,&rec[i+n].y);
        rec[i].y1=rec[i+n].y,rec[i+n].y1=rec[i].y;
        rec[i].is=0,rec[i+n].is=1;
        d[i]=rec[i].y,d[i+n]=rec[i+n].y;
    }
    sort(rec+1,rec+2*n+1,cmp);
    sort(d+1,d+2*n+1);
    cnt=unique(d+1,d+2*n+1)-d-1;
}

void solve(){
    double ans=0;
    for(int i=1;i<2*n;i++){
        int l=query(rec[i].y),r=query(rec[i].y1);
        if(!rec[i].is)modify(root,1,cnt-1,l,r-1,1);
        else modify(root,1,cnt-1,r,l-1,-1);
        ans+=(rec[i+1].x-rec[i].x)*t[root].len;
    }
    printf("Test case #%d\n",++kase);
    printf("Total explored area: %.2lf\n",ans);
    puts("");
}

int main(){
    while(scanf("%d",&n)&&n){
        memset(t,0,sizeof(t)),memset(rec,0,sizeof(rec));
        tot=root=0;
        read_and_parse();
        solve();    
    }
    return 0;
}