2284.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"algorithm"
#include"math.h"
#include"iostream.h"
#include"set"
using namespace std;

struct point
{
	double x,y;
};

struct line
{
	point a,b;
};
typedef double Type;

inline bool equal(point a,point b)
{
	return a.x==b.x&&a.y==b.y;
}

////////////////////////////////////////////////
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}


inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}

/////////////////////////////////////////
int jiao(line l1,line l2)
{Type s1=cheng(l1.a,l1.b,l2.a),
s2=cheng(l1.a,l1.b,l2.b),s3,s4;

if(s1*s2>0)return 0;

s3=cheng(l2.a,l2.b,l1.a);s4=cheng(l2.a,l2.b,l1.b);

if(s3*s4>0)return 0;

if(s1*s2<0&&s3*s4<0)return 1;

if( dcheng(l1.a,l2.a,l2.b)<0
||dcheng(l1.b,l2.a,l2.b)<0
||dcheng(l2.a,l1.a,l1.b)<0
||dcheng(l2.b,l1.a,l1.b)<0)
return 2;

return 0;

}
///////////////////////////////////
point crosspoint(line l1,line l2)
{Type p1=cheng(l2.a,l1.a,l2.b),
p2=cheng(l2.a,l2.b,l1.b);
if(p1+p2==0)return l1.a;

point c;
c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
return c;
}

///////////////////////////////////////////


line edge[400];
int n;


struct cmp
{
	bool operator()(point a,point b)const
	{
		return a.x<b.x||(fabs(a.x-b.x)<1e-8&&a.y<b.y);
	}

};

set<point,cmp> p;
set<point,cmp> p_on_l[310];

void init()
{
	point p1,p2;line lt;
	int i;
	
	p.clear();
	for(i=0;i<n;i++)
		p_on_l[i].clear();
		
	cin>>p1.x>>p1.y;

	for(i=0;i<n;i++)
	{
		cin>>p2.x>>p2.y;
		p.insert(p2);
		
		lt.a=p1;lt.b=p2;		
		edge[i]=lt;
		
		p_on_l[i].insert(p1);
		p_on_l[i].insert(p2);

		p1.x=p2.x;
		p1.y=p2.y;
	}
}


int doit()
{
	int i,j;point pt;
	
	for(i=0;i<n;i++)
	for(j=i+1;j<n;j++)
		if(jiao(edge[i],edge[j]))
		{
			pt=crosspoint(edge[i],edge[j]);
			
			if(p_on_l[i].find(pt)==p_on_l[i].end())p_on_l[i].insert(pt);
			if(p_on_l[j].find(pt)==p_on_l[j].end())p_on_l[j].insert(pt);
			if(p.find(pt)==p.end())p.insert(pt);
		}

	int m=0;
	for(i=0;i<n;i++)
		m+=p_on_l[i].size()-1;

	return m+2-p.size();
}


int main()
{
	int i=1;
	while(1)
	{
		cin>>n;
		if(n==0)break;
		n--;
		
		init();
		cout<<"Case "<<i++<<": There are "<<doit()<<" pieces."<<endl;
	}
	return 0;
}