|
Language:
Intersecting Lines
Description
求两条直线相交部分，给出的坐标的范围在 -1000 到 1000 之间且为整数.
Input
第一行为数据组数 N≤10
接下来N行，每行为x1y1x2y2x3y3x4y4.表示第一条直线过 (x1,y1) 和 (x2,y2) ，第二条过 (x3,y3) 和 (x4,y4). 保证直线能被确定.
Output
输出 N+2 第一行输出INTERSECTING LINES OUTPUT. 接下来每行输出相交部分 none, line, 或 point x y(保留2位小数). 最后1行输出 "END OF OUTPUT".
Sample Input 5 0 0 4 4 0 4 4 0 5 0 7 6 1 0 2 3 5 0 7 6 3 -6 4 -3 2 0 2 27 1 5 18 5 0 3 4 0 1 2 2 5 Sample Output INTERSECTING LINES OUTPUT POINT 2.00 2.00 NONE LINE POINT 2.00 5.00 POINT 1.07 2.20 END OF OUTPUT Source |
模板如下：
注意* 表示叉积
这题涉及已知相交，线段跨立求交点
异侧情况：
同侧情况：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define eps 1e-8
double sqr(double x) {return x*x;}
struct P
{
double x,y;
P(double _x,double _y):x(_x),y(_y){}
P(){}
double dis()
{
return sqrt(sqr(x)+sqr(y));
}
};
struct V
{
double x,y;
V(double _x,double _y):x(_x),y(_y){}
V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
V(){}
const double dis()
{
return sqrt(sqr(x)+sqr(y));
}
};
P operator+(const P a,const V b)
{
return P(a.x+b.x,a.y+b.y);
}
V operator*(const double a,const V b)
{
return V(a*b.x,a*b.y);
}
double operator*(const V a,const V b)
{
return a.x*b.y-b.x*a.y;
}
P jiao_dian(const V a,V b,const V c,const V CD,const P C)
{
double d;
d=b.dis();
double s1=a*b,s2=b*c;
double k=s1/(s1+s2);
return C+k*CD;
}
bool equal(const double a,const double b)
{
if (abs(a-b)<eps) return 1;return 0;
}
int n;
int main()
{
//s freopen("poj1269.in","r",stdin);
cout<<"INTERSECTING LINES OUTPUT"<<endl;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
double x1,y1,x2,y2,x3,y3,x4,y4;
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
P A=P(x1,y1),B=P(x2,y2),C=P(x3,y3),D=P(x4,y4);
V AB=V(A,B),AC=V(A,C),AD=V(A,D),CD=V(C,D);
if (equal((AB*CD),0))
{
if (equal((AC*AD),0)) cout<<"LINEn";
else cout<<"NONEn";
}
else
{
P p=jiao_dian(AC,AB,AD,CD,C);
cout.setf(ios::fixed);
cout.precision(2);
cout<<"POINT "<<p.x<<' '<<p.y<<endl;
}
}
cout<<"END OF OUTPUT"<<endl;
return 0;
}