ACM World Final 2008题目程序代码

				#include 
				#include 
				#include 
				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)					}
					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					}
				} 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						for(int i=1;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						{
							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;
				}