欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ - 1269 Intersecting Lines

程序员文章站 2022-04-02 16:59:33
...

题目链接

四个点,判断两条线段位置(共线,平行,相交)

平行:(B.x-A.x)*(D.y-C.y)=(B.y-A.y)*(D.x-D.x)

共线:交叉积(AC,AB)=0,交叉积(AD,AB)=0

相交:设交点为P

         则交叉积(AP,BP)=0,交叉积(CP,DP)=0

         展开为:

                     (A.y-B.y)*P.x+(B.x-A.x)*P.y+A.x*B.y-B.x*A.y=0

                     (C.y-D.y)*P.x+(D.x-C.x)*p.y+C.x*D.y-D.x*C.y=0

           化为二元一次求解即可

#include<cstdio>
#include<cmath>
using namespace std;

struct point{
	double x,y;
}p1,p2,p3,p4; 

double cal(point a,point b,point c){  //交叉积 
	double res=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
	return res; 
}

bool para(point a,point b,point c,point d){
	if((b.x-a.x)*(d.y-c.y)==(b.y-a.y)*(d.x-c.x))
		return true;
	return false;
} 

void work(){
	//line
	if(cal(p1,p2,p3)==0&&cal(p1,p2,p4)==0){
		printf("LINE\n");return ;
	}
	//parallel
	else if(para(p1,p2,p3,p4)){
		printf("NONE\n");return ;
	}
	else{
		double a1=p1.y-p2.y,b1=p2.x-p1.x,c1=p1.x*p2.y-p2.x*p1.y;
		double a2=p3.y-p4.y,b2=p4.x-p3.x,c2=p3.x*p4.y-p4.x*p3.y;
		double x0=(c1*b2-c2*b1)/(a2*b1-b2*a1);
		double y0=(c1*a2-c2*a1)/(a1*b2-b1*a2);
		printf("POINT %.2f %.2f\n", x0, y0);
	}
}

int main(){
	int n;
	while(~scanf("%d",&n)){
		printf("INTERSECTING LINES OUTPUT\n");
		
		while(n--){
			scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
			scanf("%lf%lf%lf%lf",&p3.x,&p3.y,&p4.x,&p4.y);
			work();
		}
		
		printf("END OF OUTPUT\n");
	}
	return 0;
}