求矩形面积并，周长并。
P5490 【模板】扫描线
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=400005;
ll n,ans;
struct node{
int x,yy,y;
int v;
}a[N<<1];
struct Node{
int l,r;
int len,v;
}t[N*6];
ll b[N<<1];
ll cnt;
ll read(){
ll num=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
num=num*10+c-'0';
c=getchar();
}
return f*num;
}
bool cmp(node aa,node bb){
return aa.x<bb.x;
}
void pushup(ll k){
if(t[k].v) t[k].len=b[t[k].r+1]-b[t[k].l];
else t[k].len=t[k<<1].len+t[k<<1|1].len;
}
void build(ll k,ll l,ll r){
t[k].l=l; t[k].r=r;
if(l==r) return;
ll mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(ll k,ll x,ll y,ll l,ll r,ll v){
if(l<=x&&y<=r){
t[k].v+=v;
pushup(k);
return;
}
ll mid=(x+y)>>1;
if(l<=mid) update(k<<1,x,mid,l,r,v);
if(r>mid) update(k<<1|1,mid+1,y,l,r,v);
pushup(k);
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i].x=read(); a[i].y=read(); a[i+n].x=read(); a[i].yy=read();
a[i+n].y=a[i].y; a[i+n].yy=a[i].yy; a[i].v=1; a[i+n].v=-1;
b[++cnt]=a[i].x;
b[++cnt]=a[i].y;
b[++cnt]=a[i+n].x;
b[++cnt]=a[i].yy;
}
sort(b+1,b+cnt+1);
ll m=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++){
a[i].x=lower_bound(b+1,b+m+1,a[i].x)-b;
a[i+n].x=lower_bound(b+1,b+m+1,a[i+n].x)-b;
a[i+n].y=a[i].y=lower_bound(b+1,b+m+1,a[i].y)-b;
a[i+n].yy=a[i].yy=lower_bound(b+1,b+m+1,a[i].yy)-b;
}
sort(a+1,a+n*2+1,cmp);
build(1,1,m);
for(int i=1;i<=2*n;i++){
ans+=(b[a[i].x]-b[a[i-1].x])*t[1].len;
update(1,1,m,a[i].y,a[i].yy-1,a[i].v);
}
printf("%lld",ans);
return 0;
}
hdu1542
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
typedef long long ll;
int cnt;
int n,T;
double ans;
struct node{
double x,yy,y;
int v;
}a[N<<1];
double b[N<<1];
struct Node{
double len;
int l,r;
int v;
}t[N<<3];
bool cmp(node aa,node bb){
return aa.x<bb.x;
}
void pushup(int k){
if(t[k].v) t[k].len=b[t[k].r+1]-b[t[k].l];
else t[k].len=t[k<<1].len+t[k<<1|1].len;
}
void update(int k,int l,int r,int x,int y,int v){
if(x<=l&&r<=y){
t[k].v+=v;
pushup(k);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x,y,v);
if(y>mid) update(k<<1|1,mid+1,r,x,y,v);
pushup(k);
}
void build(int k,int l,int r){
t[k].l=l; t[k].r=r;
if(l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
int main(){
while(~scanf("%d",&n)&&n!=0){
ans=0;
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i+n].x,&a[i].yy);
a[i+n].y=a[i].y; a[i+n].yy=a[i].yy;
a[i].v=1; a[i+n].v=-1;
b[++cnt]=a[i].x;
b[++cnt]=a[i].y;
b[++cnt]=a[i].yy;
b[++cnt]=a[i+n].x;
}
sort(b+1,b+cnt+1);
int m=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++){
a[i].x=lower_bound(b+1,b+m+1,a[i].x)-b;
a[i+n].x=lower_bound(b+1,b+m+1,a[i+n].x)-b;
a[i].y=a[i+n].y=lower_bound(b+1,b+m+1,a[i].y)-b;
a[i].yy=a[i+n].yy=lower_bound(b+1,b+m+1,a[i].yy)-b;
}
sort(a+1,a+n*2+1,cmp);
build(1,1,m);
for(int i=1;i<=2*n;i++){
ans+=(b[(int)a[i].x]-b[(int)a[i-1].x])*t[1].len;
update(1,1,m,a[i].y,a[i].yy-1,a[i].v);
}
printf("Test case #%d
",++T);
printf("Total explored area: %.2f
",ans);
}
return 0;
}
hdu 1828
hdu 3265