POJ 1269(直线的交点)

Language:
Intersecting Lines
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 7657   Accepted: 3510

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<<"LINE\n";
            else cout<<"NONE\n";
        } 
        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;
}