j.cpp

ACM World Final 2008题目程序代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef int (*cmpfunc)(const void*,const void*);

double hy(double x1,double x2)
{
	return sqrt(x1*x1+x2*x2);
}

double tnow,hnow,ans;
int n;

struct po
{
	double x,y;
	po(double x_=0,double y_=0):x(x_),y(y_){}
	po operator-(const po& p) const
	{
		return po(x-p.x,y-p.y);
	}
};

struct line
{
	po p1,p2;
	line& operator()(const po& p1_,const po& p2_)
	{
		return p1=p1_,p2=p2_,*this;
	}
	double y() const
	{
		return p1.y+(p2.y-p1.y)*(tnow-p1.x)/(p2.x-p1.x);
	}
};

struct
{
	double cross(const po& p1,const po& p2)
	{
		return p1.x*p2.y-p1.y*p2.x;
	}
	bool inw(const line& x1,const line& x2)
	{
		po v0=x1.p2-x1.p1,v1=x2.p1-x1.p1,v2=x2.p2-x1.p1;
		return cross(v0,v1)*cross(v0,v2)<0;
	}
	bool operator()(const line& x1,const line& x2)
	{
		return inw(x1,x2) && inw(x2,x1);
	}
	double x(const line& x1,const line& x2)
	{
		po v0=x1.p2-x1.p1,v1=x2.p1-x1.p1,v2=x2.p2-x1.p1;
		double c1=cross(v0,v1),c2=cross(v0,v2);
		return (x2.p1.x*c2-x2.p2.x*c1)/(c2-c1);
	}
} in;

struct mt
{
	double x,h,b;
	line u,d;
	int p;
	mt& read()
	{
		scanf("%lf %lf %lf",&x,&h,&b);
		x+=1e-9*rand()/RAND_MAX;
		po po1(x-0.5*b,0),po2(x,h),po3(x+0.5*b,0);
		return u(po1,po2),d(po2,po3),*this;
	}
	void addev();
	double y() const
	{
		return tnow<u.p2.x?u.y():d.y();
	}
} mo[110],*mtal[110];
int mtalsize;

struct event
{
	double t;
	int c;
	mt *no1,*no2;
	void operator()(double t_,int c_,mt* no1_=mo,mt* no2_=mo)
	{
		t=t_,c=c_,no1=no1_,no2=no2_;
	}
	void ins()
	{
		mtal[no1->p=++mtalsize]=no1;
	}
	void del()
	{
		--mtalsize;
	}
	void swp()
	{
		int p1=no1->p,p2=no2->p;
		mtal[no2->p=p1]=no2;
		mtal[no1->p=p2]=no1;
	}	
	void deal()
	{
		tnow=t;
		switch(c)
		{
			case 1:return ins();
			case 2:return del();
			case 3:return swp();
		}
	}
} ev[11000];
int evsize;

int cmpev(event* e1,event* e2)
{
	return (e1->t > e2->t) - (e1->t < e2->t);
}

void mt::addev()
{
	ev[++evsize](u.p1.x,1,this);
	ev[++evsize](u.p2.x,0);
	ev[++evsize](d.p2.x,2);
}

void addev(mt* m1,mt* m2)
{
	if(in(m1->u,m2->u))ev[++evsize](in.x(m1->u,m2->u),3,m1,m2);
	if(in(m1->u,m2->d))ev[++evsize](in.x(m1->u,m2->d),3,m1,m2);
	if(in(m1->d,m2->u))ev[++evsize](in.x(m1->d,m2->u),3,m1,m2);
	if(in(m1->d,m2->d))ev[++evsize](in.x(m1->d,m2->d),3,m1,m2);
}

int main()
{
	for(int te=1;scanf("%d",&n),n;++te)
	{
		evsize=0;
		for(int i=1;i<=n;++i)mo[i].read().addev();
		for(int i=1;i<n;++i)
			for(int j=n;j>i;--j)
				addev(&mo[i],&mo[j]);
		qsort(ev+1,evsize,sizeof(*ev),(cmpfunc)cmpev);
		mtalsize=0,ans=1e-6,tnow=hnow=0;
		for(int i=1;i<=evsize;++i)
		{
			double t0=tnow,h0=hnow;
			ev[i].deal();
			hnow=mtalsize?mtal[1]->y():0;
			if(hnow!=h0)ans+=hy(hnow-h0,tnow-t0);
		}
		printf("Case %d: %.0lf\n\n",te,ans);
	}
	return 0;
}