POJ 1269 Intersecting Lines（几何）

 1 //1269
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 #define eps 1e-8
 9 #define zero(x) (((x)>0?(x):-(x))<eps)
10 typedef struct
11 {
12     double x,y ;
13 } point ;
14 typedef struct
15 {
16     point a,b ;
17 } line ;
18 
19 //计算cross product (P1-P0)x(P2-P0)
20 double xmult(double x1,double y1,double x2,double y2,double x0,double y0)
21 {
22     return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
23 }
24 
25 //判三点共线
26 int dots_inline(double x1,double y1,double x2,double y2,double x3,double y3)
27 {
28     return zero(xmult(x1,y1,x2,y2,x3,y3));
29 }
30 
31 //线段交点请另外判线段相交(同时还是要判断是否平行!)
32 point intersection(point u1,point u2,point v1,point v2)
33 {
34     point ret=u1;
35     double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
36     ret.x+=(u2.x-u1.x)*t;
37     ret.y+=(u2.y-u1.y)*t;
38     return ret;
39 }
40 
41 int parallel(point u1,point u2,point v1,point v2)
42 {
43     return zero((u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y));
44 }
45 
46 int main()
47 {
48     int n ;
49     scanf("%d",&n) ;
50     point p1,q1,p2,q2 ;
51     printf("INTERSECTING LINES OUTPUT\n") ;
52     for(int i = 0 ; i < n ; i++)
53     {
54         scanf("%lf %lf %lf %lf",&p1.x,&p1.y,&p2.x,&p2.y) ;
55         scanf("%lf %lf %lf %lf",&q1.x,&q1.y,&q2.x,&q2.y) ;
56         if(dots_inline(p1.x,p1.y,p2.x,p2.y,q1.x,q1.y)&&dots_inline(p1.x,p1.y,p2.x,p2.y,q2.x,q2.y))
57             printf("LINE\n") ;
58         else if(parallel(p1,p2,q1,q2))
59             printf("NONE\n") ;
60         else
61         {
62             point ret = intersection(p1,p2,q1,q2) ;
63             printf("POINT %.2lf %.2lf\n",ret.x,ret.y) ;
64         }
65     }
66     printf("END OF OUTPUT\n") ;
67     return 0 ;
68 }