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

发个code纪念一下下

Posted by ACAccepted at 2019-09-28 16:52:07 on Problem 1151
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=5555;
int n,m,tot;

struct lines
{
	int mark;
	double l,r,h;
	
	lines(){}
	lines(int mark,double l,double r,double h):mark(mark),l(l),r(r),h(h){}
	
	inline bool operator < (const lines tmp) const
	{
		return h<tmp.h;
	}
}line[MAXN<<1];
double x[MAXN<<1];

namespace stree
{
	int sum[MAXN<<2];
	double len[MAXN<<2];
	
	inline void push_down(int k,int l,int r)
	{
		if (sum[k]) len[k]=x[r+1]-x[l];
		else len[k]=len[k<<1]+len[k<<1|1];
	}
	
	inline void edit_tree(int k,int l,int r,double _l,double _r,int d)
	{
		int mid=l+r>>1;
		if (_r<=x[l]||_l>=x[r+1]) return ;
		if (_l<=x[l]&&_r>=x[r+1]) sum[k]+=d;
		else edit_tree(k<<1,l,mid,_l,_r,d),edit_tree(k<<1|1,mid+1,r,_l,_r,d);
		push_down(k,l,r);
	}
}

int main()
{
	double x1,x2,y1,y2;
	int cas,t=0;
	while (~scanf("%d",&n)&&n)
	{
		m=n<<1;
		for (int i=1;i<=n;i++)
		{
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			x[(i<<1)-1]=x1;x[i<<1]=x2;
			line[(i<<1)-1]=lines(1,x1,x2,y1);
			line[i<<1]=lines(-1,x1,x2,y2);
		}
		double ans=0;
		sort(x+1,x+m+1);
		sort(line+1,line+m+1);
		x[tot=1]=x[1];for (int i=2;i<=m;i++) if (x[i]!=x[i-1]) x[++tot]=x[i];
		for (int i=1;i<m;i++)
		{
			stree::edit_tree(1,1,tot-1,line[i].l,line[i].r,line[i].mark);
			ans+=stree::len[1]*(line[i+1].h-line[i].h);
		}
		stree::edit_tree(1,1,tot-1,line[m].l,line[m].r,line[m].mark);
		printf("Test case #%d\n",++t);
		printf("Total explored area: %.2f\n\n",ans);
	}
	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