| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
带注释,详细代码// Atlantis
#include <iostream>
#include <iomanip>
#include <algorithm>
#define pb push_back
#define lc (p*2)
#define rc (p*2+1)
#define rep(i, s, t) for(int i=s; i<=t; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
#define int long long
const int SIZE=3000010;
using namespace std;
int n;
struct eachedge
{
double x, y1, y2, k;
} e[SIZE];
bool cmp(eachedge a, eachedge b)
{
if(a.x!=b.x) return a.x<b.x;
return a.k>b.k;
}
double rk[SIZE];
double raw[SIZE]; int cnt=0;
struct segmentTreeNode
{
int l, r, cnt;
double len;
// cnt: 被多少个矩形完整地包含
} t[SIZE];
void pushup(int p)
{
if(!t[p].l && !t[p].r) return; // 无用的节点
if(t[p].cnt) t[p].len=raw[t[p].r+1]-raw[t[p].l];
else t[p].len=t[lc].len+t[rc].len;
}
void build(int p, int l, int r)
{
t[p].l=l; t[p].r=r;
if(l==r) return;
int mid=(l+r)/2;
build(lc, l, mid);
build(rc, mid+1, r);
}
void change(int p, int l, int r, int v)
{
if(l<=t[p].l && t[p].r<=r)
{
t[p].cnt+=v;
pushup(p);
return;
}
int mid=(t[p].l+t[p].r)/2;
if(l<=mid) change(lc, l, r, v);
if(r>mid) change(rc, l, r, v);
pushup(p);
}
signed main()
{
int tot=1;
while(cin>>n && n)
{
cnt=0;
rep(i, 1, n)
{
double x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
// 存储抽象矩形的每一条纵边
e[i*2-1].x=x1, e[i*2-1].y1=y1, e[i*2-1].y2=y2;
e[i*2].x=x2, e[i*2].y1=y1, e[i*2].y2=y2;
e[i*2-1].k=1, e[i*2].k=-1;
// 预处理离散化
rk[++cnt]=y1, rk[++cnt]=y2;
}
sort(rk+1, rk+cnt+1);
cnt=unique(rk+1, rk+cnt+1)-rk-1;
// 处理离散化后的索引 raw
rep(i, 1, n*2)
{
int p1=lower_bound(rk+1, rk+cnt+1, e[i].y1)-rk;
int p2=lower_bound(rk+1, rk+cnt+1, e[i].y2)-rk;
raw[p1]=e[i].y1; raw[p2]=e[i].y2;
e[i].y1=p1; e[i].y2=p2;
}
// 将所有边按照 x 坐标排序并初始化线段树
sort(e+1, e+n*2+1, cmp);
build(1, 1, n*2);
// 开始扫描线算法
double ans=0;
rep(i, 1, n*2)
{
// 计算当前边对总面积的贡献
change(1, e[i].y1, e[i].y2-1, e[i].k);
ans+=t[1].len*(e[i+1].x-e[i].x);
}
cout<<"Test case #"<<tot++<<endl;
cout<<"Total explored area: "<<fixed<<setprecision(2)<<ans<<endl<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator