首页 > 代码库 > poj 1269 Intersecting Lines(判相交交点与平行)
poj 1269 Intersecting Lines(判相交交点与平行)
http://poj.org/problem?id=1269
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 10379 | Accepted: 4651 |
Description
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.
Input
Output
Sample Input
50 0 4 4 0 4 4 05 0 7 6 1 0 2 35 0 7 6 3 -6 4 -32 0 2 27 1 5 18 50 3 4 0 1 2 2 5
Sample Output
INTERSECTING LINES OUTPUTPOINT 2.00 2.00NONELINEPOINT 2.00 5.00POINT 1.07 2.20END OF OUTPUT
Source
//////////////////////////////////////////////////////////////////////////////////////////////////////
题目大意是给定n对线,判断每一对线是平行还是相交并求出交点
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <algorithm>#include <limits.h>#include <iostream>const double eps = 1e-6;typedef struct Node{ double x,y;} point;typedef struct{ point a,b;} line;bool dy(double x,double y){ return x>eps+y;}//x>ybool xy(double x,double y){ return x<y-eps;}//x<ybool dyd(double x,double y){ return x>y-eps;}//x>=ybool xyd(double x,double y){ return x<y+eps;}//x<=ybool dd(double x,double y){ return fabs(x-y)<eps;}//x==ydouble crossProduct(point a,point b,point c)//ab ac{ return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);}bool parallel(line u,line v){ return dd((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y),0.0);}point intersection(line u,line v){ point ans=u.a; double t = ((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/ ((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x)); ans.x+=(u.b.x-u.a.x)*t; ans.y+=(u.b.y-u.a.y)*t; return ans;}int main(){ line u,v; int n; while(scanf("%d",&n)!=EOF) { printf("INTERSECTING LINES OUTPUT\n"); while(n--) { scanf("%lf%lf%lf%lf",&u.a.x,&u.a.y,&u.b.x,&u.b.y); scanf("%lf%lf%lf%lf",&v.a.x,&v.a.y,&v.b.x,&v.b.y); if(parallel(u,v)) { if(dd(crossProduct(u.a,u.b,v.a),0.0)) printf("LINE\n"); else printf("NONE\n"); } else { point ans=intersection(u,v); printf("POINT %.2lf %.2lf\n",ans.x,ans.y); } } printf("END OF OUTPUT\n"); }}
由于并不是太懂,就拷贝别人的了
原帖:http://blog.csdn.net/zxy_snow/article/details/6341282
/×
先判断两条直线是不是同线,不是的话再判断是否平行,再不是的话就只能是相交的,求出交点。
如何判断是否同线?由叉积的原理知道如果p1,p2,p3共线的话那么(p2-p1)X(p3-p1)=0。因此如果p1,p2,p3共线,p1,p2,p4共线,那么两条直线共线。direction()求叉积,叉积为0说明共线。
如何判断是否平行?由向量可以判断出两直线是否平行。如果两直线平行,那么向量p1p2、p3p4也是平等的。即((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x))==0说明向量平等。
如何求出交点?这里也用到叉积的原理。假设交点为p0(x0,y0)。则有:
(p1-p0)X(p2-p0)=0
(p3-p0)X(p2-p0)=0
展开后即是
(y1-y2)x0+(x2-x1)y0+x1y2-x2y1=0
(y3-y4)x0+(x4-x3)y0+x3y4-x4y3=0
将x0,y0作为变量求解二元一次方程组。
假设有二元一次方程组
a1x+b1y+c1=0;
a2x+b2y+c2=0
那么
x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
因为此处两直线不会平行,所以分母不会为0。
×/