1269.txt

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

#include"iostream.h"
#include"stdio.h"
#include"math.h"
struct point
{double x,y;};
	

struct line
{double a,b,c;};
struct linet
{point a,b;};


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

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

int judge(linet l1,linet l2)
{double s1=cheng(l1.a,l1.b,l2.a),
	s2=cheng(l1.a,l1.b,l2.b),
	s3=cheng(l2.a,l2.b,l1.a),
	s4=cheng(l2.a,l2.b,l1.b);
	if(s1==0&&s2==0&&s3==0&&s4==0)return 1;

	if((l1.a.x-l1.b.x)*(l2.a.y-l2.b.y)-(l1.a.y-l1.b.y)*(l2.a.x-l2.b.x)==0)
		return 2;
	return 3;
}
struct ray
{point p;
	double dx,dy;};

line ray_line(ray s)
{line l;double d;
	if(s.dx==0){l.a=1;l.b=0;l.c=-s.p.x;return l;}	
	d=s.dy/s.dx;
	l.a=d;l.b=-1;l.c=s.p.y-d*s.p.x;
	return l;
}
point jiao(line &l1,line &l2)
{point n;
	n.y=(l1.a*l2.c-l2.a*l1.c)/(l2.a*l1.b-l1.a*l2.b);
	n.x=(l2.c*l1.b-l1.c*l2.b)/(l1.a*l2.b-l2.a*l1.b);
	return n;
}

int main()
{int t;line l1,l2;ray r1,r2;double a,b;point n;linet t1,t2;
	cin>>t;
	printf("INTERSECTING LINES OUTPUT\n");
	while(t--)
	{cin>>r1.p.x>>r1.p.y>>a>>b;
	r1.dx=a-r1.p.x;
	r1.dy=b-r1.p.y;
	l1=ray_line(r1);	
	t1.a=r1.p;t1.b.x=a;t1.b.y=b;
	
	cin>>r2.p.x>>r2.p.y>>a>>b;
        r2.dx=a-r2.p.x;
        r2.dy=b-r2.p.y;
        l2=ray_line(r2);
	t2.a=r2.p;t2.b.x=a;t2.b.y=b;
	
	switch(judge(t1,t2))
	{case 1:printf("LINE\n");break;
	 case 2:printf("NONE\n");break;
	 case 3:printf("POINT ");n=jiao(l1,l2);
		printf("%.2f %.2f\n",n.x,n.y);
		break;
	}
	}
	printf("END OF OUTPUT\n");
return 0;
}