题目描述
线段树+扫描线
经典恶心题
最后输出有坑,每个样例一个空行
样例
2
10 10 20 20
15 15 25 25.5
0
Test case #1
Total explored area: 180.00
算法1
(暴力枚举) $O(n^2)$
开始y总数据开的100,暴力直接过。
时间复杂度
$O(n^2)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct rec{double x;int to,e;}a[210],b[210];
int c[110][2],f[210],n,i,j,k,x,y,z,data;
double len,ans,x1,y1,x2,y2;
int cmp(const void *a,const void *b)
{
return ((rec *)a)->x>((rec *)b)->x?1:-1;
}
int main()
{
while(cin>>n&&n)
{
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
a[i*2-1].x=x1; a[i*2-1].to=i; a[i*2-1].e=1;
a[i*2].x=x2; a[i*2].to=i; a[i*2].e=-1;
b[i*2-1].x=y1; b[i*2-1].to=i; b[i*2-1].e=0;
b[i*2].x=y2; b[i*2].to=i; b[i*2].e=1;
}
qsort(b+1,2*n,sizeof(b[1]),cmp);
qsort(a+1,2*n,sizeof(a[1]),cmp);
for(i=1;i<=2*n;i++) c[b[i].to][b[i].e]=i;
memset(f,0,sizeof(f));
for(ans=0,i=1;i<2*n;i++)
{
j=a[i].to; x=c[j][0]; y=c[j][1]; z=a[i].e;
for(k=x;k<y;k++) f[k]+=z;
for(len=0,k=1;k<2*n;k++) if(f[k]) len+=b[k+1].x-b[k].x;
ans+=len*(a[i+1].x-a[i].x);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++data,ans);
}
return 0;
}
算法2
(线段树+扫描线) $O(nlogn)$
线段树+扫描线
注意点:
线段树维护的是区间并不是结点,所以m个点,我们只需要维护m-1个区间;
同时$y1\longrightarrow y2$是一个区间,所以我们如果要修改整个大区间的值只需要从$y_{1}\longrightarrow y_{m-1}$.
时间复杂度
$O(nlogn)$.
参考文献
https://blog.csdn.net/riba2534/article/details/76851233
https://www.acwing.com/solution/content/1027/
C++ 代码
/*
* Filename: d:\test1\cpp1\Acwing\247.cpp
* Path: d:\test1\cpp1\Acwing
* Created Date: Monday, July 4th 2022, 7:50:00 pm
* Author: Waitsnow
*
* Copyright (c) 2022 Your Company
*/
#include <bits/stdc++.h>
#define ls (p << 1)
#define rs (ls | 1)
#define mid ((t[p].l + t[p].r) >> 1)
using namespace std;
const int N = 1e5 + 6;
int n, m, num;
struct P
{
double x,y,z;
int k;
inline bool operator<(const P &t)const
{
return x<t.x;
}
}a[N];
double raw[N<<1];
map<double, int> val;
struct T
{
int l,r,cnt;
double len;
}t[N*8];
void build(int p, int l, int r) {
t[p].l=l,t[p].r=r,t[p].cnt=0,t[p].len=0;
if(l==r)return ;
build(ls,l,mid),build(rs,mid+1,r);
}
void change(int p, int l, int r, double k) {
if(l<=t[p].l&&r>=t[p].r)
{
t[p].len=(t[p].cnt+=k)?raw[t[p].r+1]-raw[t[p].l]:(t[p].l==t[p].r)?0:t[ls].len+t[rs].len;
return ;
}
if(l<=mid)change(ls,l,r,k);
if(r>mid) change(rs,l,r,k);
t[p].len=t[p].cnt?raw[t[p].r+1]-raw[t[p].l]:t[ls].len+t[rs].len;
}
inline void Atlantis() {
for(int i=1;i<=n;i++)
{
int k=2*i;
double y1,y2;
scanf("%lf%lf%lf%lf",&a[k-1].x,&y1,&a[k].x,&y2);
raw[k-1]=a[k-1].y=a[k].y=y1;
raw[k]=a[k-1].z=a[k].z=y2;
a[k-1].k=1,a[k].k=-1;
}
n<<=1;
sort(raw+1,raw+n+1);
int m=unique(raw+1,raw+n+1)-(raw+1);
for(int i=1;i<=m;i++)val[raw[i]]=i;
sort(a+1,a+n+1);
build(1,1,m-1);
double ans=0;
for(int i=1;i<n;i++)
{
int y=val[a[i].y],z=val[a[i].z]-1;
change(1,y,z,a[i].k);
ans+=t[1].len*(a[i+1].x-a[i].x);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n", ++num, ans);
}
int main() {
while (cin >> n && n) Atlantis();
return 0;
}