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; }
