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

带注释,详细代码

Posted by Jerrywang2009 at 2022-12-08 20:43:16 on Problem 1151
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator