传送门(欢迎大家来caioj 体验我出的良(er)心数据.)
扫描线模板题
因为n很小、横纵坐标又可能是实数，所以我们很自然地想到离散化。
我们考虑有一条水平线从上到下扫描整个图形。像这样：
我们可以发现,直线被截取的长度只有可能在矩形的上下界发生变化.
我们把横坐标离散化、去重，把区域分成若干份。像这样：
去重后得到8个坐标，可以分出7个块。
假设纵坐标也这样分。像这样：
这样我们就把图割成了若干块。
考虑暴力
因为是从上往下扫，所以我们把上面的边定义为入边，下面的边定义为出边。
每加入一条入边，对应区域覆盖+1。出边则-1。
函数
unique函数的函数原型如下：
1.只有两个参数，且参数类型都是迭代器：
iterator unique(iterator it_1,iterator it_2);
这种类型的unique函数是我们最常用的形式。其中这两个参数表示对容器中[it_1，it_2)范围的元素进行去重(注：区间是前闭后开，即不包含it_2所指的元素),返回值是一个迭代器，它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
迭代器又是什么鬼
迭代器是一个复杂的指针,你把它理解为一个地址就行.
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=410;
struct matrix{double x1,y1,x2,y2;}a[N];
struct line
{
int x,xx,v;double y;
bool operator <(line a)const{return y<a.y;}
}b[N<<1];//n*2条线段
double x[N<<1],y[N<<1];int xl,yl;
int vis[N<<1];//按横坐标分的块被覆盖的次数.
//扫描线每下移一次(运动到就近的边)就要用被覆盖的区域的长度乘上扫描线运动的长度来更新面积.
double ans;
int main()
{
int tot=1,n,m;
while(scanf("%d",&n),n)
{
m=n<<1;
for(int i=1,j=1;i<=n;i++)
{
scanf("%lf %lf %lf %lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
x[j]=a[i].x1;y[j++]=a[i].y1;
x[j]=a[i].x2;y[j++]=a[i].y2;
}
sort(x+1,x+m+1);sort(y+1,y+m+1);
xl=unique(x+1,x+m+1)-(x+1);yl=unique(y+1,y+m+1)-(y+1);
for(int i=1,j=1;i<=n;i++)
{
b[j].x=lower_bound(x+1,x+xl+1,a[i].x1)-x;
b[j].xx=lower_bound(x+1,x+xl+1,a[i].x2)-(x+1);//为什么要减一,因为我们在乎的不是点啊.
b[j].y=a[i].y2;
b[j++].v=1;//入边
b[j].x=b[j-1].x;
b[j].xx=b[j-1].xx;
b[j].y=a[i].y1;
b[j++].v=-1;//出边
}
sort(b+1,b+m+1);//一系列排序复杂度O(n logn)
ans=0;
b[0].y=y[1]-1;
for(int i=yl,j=m;i;i--)//i为纵坐标标号,j为线段标号
{
for(int k=1;k<xl;k++)
if(vis[k])
ans+=(x[k+1]-x[k])*(y[i+1]-y[i]);
while(b[j].y==y[i])
{
for(int k=b[j].x;k<=b[j].xx;k++)
vis[k]+=b[j].v;
j--;
}
}//每条线段枚举一次,一次O(n)——复杂度O(n*n)
printf("Test case #%d
",tot++);
printf("Total explored area: %.2lf
",ans);//注意:两个换行
}
return 0;
}
正解
for(int i=yl,j=m;i;i--)//i为纵坐标标号,j为线段标号
{
for(int k=1;k<xl;k++)
if(vis[k])
ans+=(x[k+1]-x[k])*(y[i+1]-y[i]);
while(b[j].y==y[i])
{
for(int k=b[j].x;k<=b[j].xx;k++)
vis[k]+=b[j].v;
j--;
}
}
我们可以看到上面有区间修改,所以我们可以用线段树来统计吗.
代码:
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define g getchar()
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=110;
int n,m,num;
struct line {//线
double x,y,z;
int k;
bool operator <(line b) const {
return x<b.x;
}
}a[N<<1];
double raw[N<<1];//纵坐标
void disc() {
sort(raw+1,raw+n+1);m=1;
for(int i=2;i<=n;i++)
if(raw[i]!=raw[m])raw[++m]=raw[i];
}
int val(double x) {
int l=1,r=m,mid;
while(l<r) {
mid=(l+r)>>1;
if(raw[mid]<x)l=mid+1;
else r=mid;
}
return l;
}
struct node {
int cnt;//区间覆盖次数
double len;
}tr[N<<3];
void bt(int x,int l,int r) {
tr[x].cnt=tr[x].len=0;
if(l==r)return ;
int mid=(l+r)>>1;
bt(lc,l,mid);
bt(rc,mid+1,r);
}
void change(int x,int l,int r,int L,int R,int k) {
if(L<=l&&r<=R) {
tr[x].cnt+=k;
if(tr[x].cnt) tr[x].len=raw[r+1]-raw[l];
else if(l==r) tr[x].len=0;
else tr[x].len=tr[lc].len+tr[rc].len;
return ;
}
int mid=(l+r)>>1;
if(L<=mid) change(lc,l,mid,L,R,k);
if(mid< R) change(rc,mid+1,r,L,R,k);
if(!tr[x].cnt) tr[x].len=tr[lc].len+tr[rc].len;
}
void qr(int &x) {
char c=g;x=0;
while(!isdigit(c))c=g;
while(isdigit(c))x=x*10+c-'0',c=g;
}
void qr(double &x) {
char c=g;x=0;int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=g;}
while(isdigit(c))x=x*10+c-'0',c=g;
if(c=='.') {
double w=0.1; c=g;
while(isdigit(c))
x+=w*(c-'0'),w/=10,c=g;
} x*=f;
}
int main() {
while(qr(n),n) {
for(int i=1,j=2;i<=n;i++,j+=2) {
double x,xx,y,z;
qr(x);qr(y);qr(xx);qr(z);
a[j-1]=(line){x,y,z,1};
a[j ]=(line){xx,y,z,-1};
raw[j-1]=y;
raw[j ]=z;
}
n <<= 1; disc() ;sort(a+1,a+n+1);
bt(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,1,m-1,y,z,a[i].k);
ans+=tr[1].len*(a[i+1].x-a[i].x);
}
printf("Test case #%d
",++num);
printf("Total explored area: %.2lf
",ans);
}
return 0;
}