Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 必须ac（用c++11才能过）

Posted by 080528lj at 2021-08-27 20:38:17 on Problem 1151
```用一个线段树加上一个离散化就可以了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int N=100010;

int n;
struct Segment
{
double x;
double y1,y2;
int k;
bool operator< (const Segment &t)const
{
return x<t.x;
}
}seg[N*2];

struct Node
{
int l;
int r;
int cnt;
double len;
}tr[N*8];

vector<double> ys; // 离散化

int find(double y)
{
return lower_bound(ys.begin(),ys.end(),y)-ys.begin(); // 二分
}

void pushup(int u)
{
if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
else if(tr[u].l == tr[u].r) tr[u].len=0;
else tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}

void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,0,0};
else
{
tr[u]={l,r};
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
}

void modify(int u,int l,int r,int k)
{
if(tr[u].l>=l && tr[u].r<=r)
{
tr[u].cnt+=k;
pushup(u);
}
else
{
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
}

int main()
{
int t=0;
while(scanf("%d",&n),n)
{
ys.clear();
for(int i=0,j=0;i<n;i++)
{
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
seg[j++]={x1,y1,y2,1};
seg[j++]={x2,y1,y2,-1};
ys.push_back(y1);
ys.push_back(y2);
}
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
build(1,0,ys.size()-2);
sort(seg,seg+n*2);

double res=0;
for(int i=0;i<n*2;i++)
{
if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);
modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
}

cout<<"Test case #"<<++t<<endl;
printf("Total explored area: ");
printf("%.2lf\n\n",res);
}
return 0;
}```

Followed by: