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 wocha at 2012-07-23 14:28:42 on Problem 1151
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define M 400+44
using namespace std;
struct note
{
	int left;
	int right;
	int cover;
	double len;
	double ly,ry;
}tree[M*4];
struct Line
{
	double x,y1,y2;
	int flag;
	
}line[M];
double y[M];
bool cmp(Line a,Line b)
{
	return a.x<b.x;
}
void build(int l,int r,int i)
{
	tree[i].left=l;
	tree[i].right=r;
	tree[i].cover=0;
	tree[i].len=0;
	tree[i].ly=y[l];
	tree[i].ry=y[r];
	if(l+1==r) return;
	int mid=(l+r)>>1;
	build(l,mid,i<<1);
	build(mid,r,i<<1|1);
};
void update(int i,Line line1)
{
	if(tree[i].ly>=line1.y1&&tree[i].ry<=line1.y2)
	{
		tree[i].cover+=line1.flag;
		if(tree[i].cover>0)
		{
			tree[i].len=tree[i].ry-tree[i].ly;
		}
		else if(tree[i].left+1==tree[i].right)
		{
			tree[i].len=0;
		}
		else 
		{
			tree[i].len=tree[i<<1].len+tree[i<<1|1].len;
		}
		return;
	}
	if(line1.y1>=tree[i<<1|1].ly)     update(i<<1|1,line1);
	else if(line1.y2<=tree[i<<1].ry)  update(i<<1,line1);
	else
	{
		update(i<<1|1,line1);
		update(i<<1,line1);
	}
	if(tree[i].cover==0)
	tree[i].len=tree[i<<1].len+tree[i<<1|1].len;
}
int main()
{
  int N;
  int o=0;
  while(cin>>N,N)
  {
  	int t=1,j=1,p=0;
 
  	for(int i=1;i<=N;i++)
  	{
	  double a,b,c,d;
      cin>>a>>b>>c>>d;
      y[j++]=b;
      y[j++]=d;
      line[t].flag=1;
      line[t].x=a;
	  line[t].y1=b;
	  line[t].y2=d;
	  t++;
	  line[t].flag=-1;
      line[t].x=c;
      line[t].y1=b;
	  line[t].y2=d;
	  t++;
 	}
 	sort(y+1,y+t);
 	sort(line+1,line+t,cmp);
    double s=0.0;
   	build (1,t-1,1);
    update(1,line[1]);
   for(int i=2;i<t;i++)
   {
    s+=tree[1].len*(line[i].x-line[i-1].x);	
    update(1,line[i]);
   }
   if(o!=0)
   printf("\n");
   printf("Test case #%d\nTotal explored area: ",++o); 

   printf("%.2f\n",s);
   
  }	
}
 

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