题意

求一个矩形的面积并

题解

师姐写的很好
然后这是一个裸题

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAX=(1<<28);
const int N=1005;
double s[N][4];
struct qt
{int x,y;double d;
}p[N];int tot;
struct qr {int l,r;double d;int o; }h[N];
bool cmp (qt x,qt y)    {
   return x.d<y.d;}
double A[N];
struct qq {int l,r;double o;double c;int s1,s2,tag; }tr[N*2];int num;
void bt (int l,int r)
{int a=++num;tr[a].l=l;tr[a].r=r;tr[a].c=tr[a].tag=0;tr[a].o=A[r+1]-A[l];tr[a].s1=tr[a].s2=0;if (l==r) return ;int mid=(l+r)>>1;tr[a].l=l;tr[a].r=r;tr[a].s1=num+1;bt(l,mid);tr[a].s2=num+1;bt(mid+1,r);
}
void update (int now)
{int s1=tr[now].s1,s2=tr[now].s2;if (tr[now].tag>0)  tr[now].c=tr[now].o;else tr[now].c=tr[s1].c+tr[s2].c;
}
void change (int now,int l,int r,int o)
{
//  printf("%d %d %d\n",l,r,o);if (tr[now].l==l&&tr[now].r==r) {
   tr[now].tag+=o;update(now);return ;}int s1=tr[now].s1,s2=tr[now].s2;int mid=(tr[now].l+tr[now].r)>>1;if (r<=mid) change(s1,l,r,o);else if (l>mid) change(s2,l,r,o);else change(s1,l,mid,o),change(s2,mid+1,r,o);update(now);
}
bool cmp1 (qr x,qr y){
   return x.d<y.d;}
int main()
{for (int T=1;;T++){tot=0;int n;scanf("%d",&n);if (n==0) break;for (int u=1;u<=n;u++)for (int i=0;i<=3;i++){scanf("%lf",&s[u][i]);if (i%2==0) p[++tot].d=s[u][i],p[tot].x=u,p[tot].y=i;}sort(p+1,p+1+tot,cmp);int mx=0;p[0].d=MAX;for (int u=1;u<=tot;u++){if (p[u].d!=p[u-1].d) mx++,A[mx]=p[u].d;s[p[u].x][p[u].y]=mx;}num=0;bt(1,mx-1);/*for (int u=1;u<=num;u++)printf("%d %d %d %lf %lf\n",tr[u].l,tr[u].r,tr[u].tag,tr[u].c,tr[u].o);*/tot=0;for (int u=1;u<=n;u++){if (s[u][1]>s[u][3]) swap(s[u][1],s[u][3]);if (s[u][0]>s[u][2]) swap(s[u][0],s[u][2]);h[++tot].l=(int)s[u][0];h[tot].r=(int)s[u][2];h[tot].d=s[u][1];h[tot].o=1;h[++tot].l=(int)s[u][0];h[tot].r=(int)s[u][2];h[tot].d=s[u][3];h[tot].o=-1;}sort(h+1,h+1+tot,cmp1);double w,H,ans=0;change(1,h[1].l,h[1].r-1,h[1].o);for (int u=2;u<=tot;u++){H=h[u].d-h[u-1].d;w=tr[1].c;//printf("%lf %lf\n",w,H);ans=ans+w*H;change(1,h[u].l,h[u].r-1,h[u].o);}printf("Test case #%d\nTotal explored area: %.2lf\n\n",T,ans);}return 0;
}