h.cpp

ACM World Final 2008题目程序代码

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

int tnow=0,n,mdep;
bool can;

struct po
{
	int x,y;
	po(){}
	po(int x_,int y_):x(x_),y(y_){}
	void read()
	{
		scanf("%d %d",&x,&y);
	}
	bool operator<(const po& p) const
	{
		return x<p.x || x==p.x && y<p.y;
	}
	po operator-(const po& p) const
	{
		return po(x-p.x,y-p.y);
	}
};

struct line
{
	po p1,p2;
	void *f;
	line(const po& p1_,const po& p2_,void* f_):p1(p1_),p2(p2_),f(f_){}
	double y() const
	{
		return p1.y+(p2.y-p1.y)*(tnow+1e-6-p1.x)/(p2.x+1e-6-p1.x);
	}
	bool operator<(const line& x) const
	{
		return y()<x.y();
	}
};

struct intype
{
	long long cross(const po& p1,const po& p2)
	{
		return (long long)p1.x*p2.y-(long long)p1.y*p2.x;
	}
	int sgn(long long x)
	{
		return x>0?1:x<0?-1:0;
	}
	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 sgn(cross(v0,v1))*sgn(cross(v0,v2))<=0;
	}
	bool operator()(const line& x1,const line& x2)
	{
		return x1.f!=x2.f && inw(x1,x2) && inw(x2,x1);
	}
} in;

#define L first
#define depth second
struct lset:multimap<line,int>
{
	typedef iterator it;
	void init()
	{
		clear();
		const int max=200000,min=-max;
		insert(pair<line,int>(line(po(min,min),po(max,min),NULL),1));
		insert(pair<line,int>(line(po(min,max),po(max,max),NULL),0));
	}
	it ins(const line& x,int d=0)
	{
		it c=insert(pair<line,int>(x,d)),p=c,n=c;
		if(in(c->L,(--p)->L) || in(c->L,(++n)->L))can=false;
		return c;
	}
	void cd(const it& x1,const it& x2)
	{
		it x0=x1;
		x1->depth=(--x0)->depth+1;
		if(x1->depth>mdep)mdep=x1->depth;
		x2->depth=x0->depth;
	}
	void del(const it& x)
	{
		if(in((--it(x))->L,(++it(x))->L))can=false;
		erase(x);
	}
} ls;

struct tri
{
	po p1,p2,p3;
	lset::it p12,p13,p23;
	tri& read()
	{
		po t;
		p1.read(),p2.read(),p3.read();
		if(p2<p1)t=p1,p1=p2,p2=t;
		if(p3<p2)t=p2,p2=p3,p3=t;
		if(p2<p1)t=p1,p1=p2,p2=t;
		return *this;
	}
	void addev(int no);
	void ins()
	{
		p12=ls.ins(line(p1,p2,this));
		p13=ls.ins(line(p1,p3,this));
		++lset::it(p12)==p13?ls.cd(p12,p13):ls.cd(p13,p12);
	}
	void ch()
	{
		p23=ls.ins(line(p2,p3,this),p12->depth);
		ls.del(p12);
	}
	void del()
	{
		ls.del(p13);
		ls.del(p23);
	}
} tr[110000];

struct event
{
	int t,w,no;
	bool operator<(const event& e) const
	{
		return t<e.t || t==e.t && w<e.w;
	}
	event& operator()(int t_,int w_,int no_)
	{
		return t=t_,w=w_,no=no_,*this;
	}
	void deal() const
	{
		tnow=t;
		switch(w)
		{
			case 1:return tr[no].ins();
			case 2:return tr[no].ch();
			case 3:return tr[no].del();
		}
	}
} ev[330000];
int evsize;
int cmp_event(const event& x1,const event& x2)
{
	return (x2<x1)-(x1<x2);
}

void tri::addev(int no)
{
	ev[++evsize](p1.x,1,no);
	ev[++evsize](p2.x,2,no);
	ev[++evsize](p3.x,3,no);
}

int main()
{
	for(int te=1;scanf("%d",&n),n!=-1;++te)
	{
		evsize=0,can=true,mdep=1,ls.init();
		for(int i=1;i<=n;++i)tr[i].read().addev(i);
		qsort(ev+1,evsize,sizeof(*ev),(cmpfunc)cmp_event);
		for(int i=1;i<=evsize && can;++i)ev[i].deal();
		if(can)printf("Case %d: %d shades\n",te,mdep);
		else printf("Case %d: ERROR\n",te);
	}
	return 0;
}