扫描线,顾名思义就是从左往右扫过去的一条线。
根据这个性质,可以转化题目,将矩形的左右边界枚举出来,形成两个四元组$(x_1,y_1,y_2,1),(x_2,y_1,y_2,-1)$
按$x$排序之后,就是一条从左往右扫的线。
这时就可以用线段树来维护当前扫描线经过的$y$值的和,线段树每一个点表示区间$[raw(i),raw(i+1)]$。
用$c[i]$表示第i段$y$值覆盖次数,答案就为:$\sum_{c[i]>0}raw(i+1)-raw(i)*(x_2-x)$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define eps 1e-6
#define ll long long
using namespace std;
const int N=105;
template<class lb>
inline void qr(lb &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node{double x,y1,y2;int k;bool operator <(const node a)const{return x<a.x;}}a[N<<1];
double arr[N<<1];int n,len;
inline void disc()
{
sort(arr+1,arr+n+1);len=0;
for(int i=1;i<=n;i++)
if(i==1||arr[i-1]!=arr[i])arr[++len]=arr[i];
}
inline int get(double val)
{
int l=1,r=len;
while(l<r)
{
int mid=l+r>>1;
if(arr[mid]-val<-eps)l=mid+1;
else r=mid;
}
return l;
}
struct Seg{int l,r,cnt;double len;}t[N<<4];
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].len=t[p].cnt=0;
if(l==r)return ;
int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void change(int p,int ql,int qr,int k)
{
if(ql<=t[p].l&&qr>=t[p].r)
{
t[p].cnt+=k;
if(t[p].cnt>0)t[p].len=arr[t[p].r+1]-arr[t[p].l];
else if(t[p].l==t[p].r)t[p].len=0;
else t[p].len=t[p<<1].len+t[p<<1|1].len;
return ;
}
int mid=t[p].l+t[p].r>>1;
if(ql<=mid)change(p<<1,ql,qr,k);
if(qr>mid)change(p<<1|1,ql,qr,k);
if(!t[p].cnt)t[p].len=t[p<<1].len+t[p<<1|1].len;
}
void qr(double &x)
{
char c=gc;double f=1,y=1;x=0;
while(!( ('0'<=c&&c<='9') || c=='-'))c=gc;
if(c=='-')f=-f,c=gc;
while('0'<=c&&c<='9')x=x*10+c-'0',c=gc;
if(c=='.')
{
c=gc;
while('0'<=c&&c<='9')y/=10.0,x+=(c-'0')*y,c=gc;
}
x*=f;
}
int T;
void Anti()
{
++T;printf("Test case #%d\n",T);
printf("Total explored area: ");
for(int i=1;i<=n;i++)
{
int k=i<<1;
double x1,x2,y1,y2;qr(x1),qr(y1),qr(x2),qr(y2);
a[k-1]=(node){x1,y1,y2,1};a[k]=(node){x2,y1,y2,-1};
arr[k-1]=y1;arr[k]=y2;
}
n<<=1;
sort(a+1,a+n+1);
disc();
build(1,1,len);
double ans=0;
for(int i=1;i<n;i++)
{
int y1=get(a[i].y1),y2=get(a[i].y2)-1;
change(1,y1,y2,a[i].k);
ans+=(a[i+1].x-a[i].x)*t[1].len;
}
printf("%.2lf\n",ans);
puts("");
}
int main()
{
while(scanf("%d",&n)&&n)Anti();
return 0;
}
最后一次更新于2019-10-11
0 条评论