2462.txt

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

Memory:116K  Time:187MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"stdio.h"
#include"math.h"
#include<vector>
#include<algorithm>



using namespace std;

/////////////////////////
#define Type double /*坐标类型*/
/////////////////////////

const double eps=1e-9;

struct point
{Type x,y;
point(){x=y=0;}
point(Type &x,Type &y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

const double pi=3.14159265359;

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 dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}

////////////////////////////////////////////
//求交点
//判断l1,l2不重合 先!!!

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;
}

int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}



inline double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

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

line l[1010];
point p[1010];
point q[1010];
int n,m;

bool init()
{
	int i;
	cin>>n>>m;
	
	if(n==0&&m==0)return 0;

	for(i=0;i<n;i++)
		cin>>p[i].x>>p[i].y;

	for(i=0;i<n;i++)
		l[i].a=p[i],l[i].b=p[(i+1)%n];
	return 1;
}

int in(point *p,int n,point judge)
{int c,j,k;point up,low,temp; 

c=0;j=0;

while(p[j].y==judge.y)j++;

for(;j<n;j=k)
{ k=j+1;

while(p[k%n].y==judge.y&&p[k%n].x>judge.x)k++;

up=p[j];

low=p[k%n];

if(up.y<low.y){temp=up;up=low;low=temp;}

if(up.y<judge.y||low.y>judge.y)continue;

if(cheng(low,up,judge)<=eps&&k==j+1)continue;

c++;

}

if(c%2)return 1;
else return 0;

}

void doit()
{
	double s1,s2,ans=0;
	int i,j,h,k,jj;
	point p1;
	
	line ls;
	cin>>ls.a.x>>ls.a.y>>ls.b.x>>ls.b.y;
	
	ls.b.x+=(ls.b.x-ls.a.x)*100;
	ls.b.y+=(ls.b.y-ls.a.y)*100;
	
	s2=cheng(p[0],ls.a,ls.b);
	
	for(h=0,i=0;i<n;i++)
	{
		s1=s2;
		s2=cheng(p[(i+1)%n],ls.a,ls.b);
		
		if(fabs(s1)<eps)
			q[h++]=p[i];
		else if(fabs(s2)>eps&&s1*s2<0)
		{
			q[h++]=crosspoint(ls,l[i]);
		}
	}
	
	sort(q,h);
	k=0;

	
	for(ans=0,jj=0;jj<h-1;jj++)
	{
		i=(k+jj)%h;
		p1.x=(q[i].x+q[(i+1)%h].x)/2;
		p1.y=(q[i].y+q[(i+1)%h].y)/2;
		for(j=0;j<n;j++)
			if(fabs(cheng(p1,l[j].a,l[j].b))<eps&&
				dcheng(p1,l[j].a,l[j].b)<=0 )
			break;
	
		if(j<n||in(p,n,p1))
		{
			ans+=dis(q[i],q[(i+1)%h]);
		}
	}

	printf("%.3f\n",ans);
}

int main()
{
	int i;
	while(init())
	{
		for(i=0;i<m;i++)
			doit();
	}
	return 0;
}