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
Mid-Atlantic 1996
 
模板如下：
注意* 表示叉积
这题涉及已知相交，线段跨立求交点
 
 
[cpp]  
#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;  
}

补充：软件开发 , C++ ,