判断线段是否有交点并求交点

  1 /*cug_1078判断线段是否有交点并求交点*/
  2 #include <stdio.h> 
  3 #include <stdlib.h> 
  4 #include <math.h> 
  5 
  6 const double eps = 1e-6; 
  7 
  8 typedef struct TPodouble  
  9 { 
 10     double x; 
 11     double y; 
 12 }TPodouble; 
 13 
 14 typedef struct TLine 
 15 { 
 16     double a, b, c; 
 17 }TLine; 
 18 
 19 double max(double x, double y) 
 20 { 
 21     if(x > y) return x; 
 22     else return y;  
 23 } 
 24 
 25 double min(double x, double y) 
 26 { 
 27     if(x < y) return x; 
 28     else return y;  
 29 } 
 30 double multi(TPodouble  p1, TPodouble  p2, TPodouble  p0) 
 31 { 
 32     return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); 
 33 } 
 34 
 35 TLine lineFromSegment(TPodouble p1, TPodouble p2) 
 36 { 
 37     TLine tmp; 
 38     tmp.a = p2.y - p1.y; 
 39     tmp.b = p1.x - p2.x; 
 40     tmp.c = p2.x * p1.y - p1.x * p2.y; 
 41     return tmp; 
 42 } 
 43 
 44 void Linedoubleer(TLine l1, TLine l2) 
 45 { 
 46     double x, y; 
 47     double a1 = l1.a; 
 48     double b1 = l1.b; 
 49     double c1 = l1.c; 
 50     double a2 = l2.a; 
 51     double b2 = l2.b; 
 52     double c2 = l2.c; 
 53     if(b1 == 0){ 
 54         x = -c1 / (double)a1;   
 55         y = (-c2 - a2 * x) / (double)b2; 
 56     }        
 57     else{ 
 58         x = (double)(c1 * b2 - b1 * c2) / (double)(b1 * a2 - b2 * a1); 
 59         y = (double)(-c1 - a1 * x) /(double)b1; 
 60     } 
 61     printf("%.3lf %.3lf
", x, y); 
 62 } 
 63 
 64 bool isIntersected(TPodouble s1, TPodouble e1, TPodouble s2, TPodouble e2){ 
 65 
 66     if( 
 67     (max(s1.x, e1.x) >= min(s2.x, e2.x)) && 
 68     (max(s2.x, e2.x) >= min(s1.x, e1.x)) && 
 69     (max(s1.y, e1.y) >= min(s2.y, e2.y)) && 
 70     (max(s2.y, e2.y) >= min(s1.y, e1.y)) && 
 71     (multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) && 
 72     (multi(s1, e2, s2) * multi(e2, e1, s2) >= 0) 
 73     )  return true; 
 74      
 75     return false;     
 76 } 
 77 
 78 double dis(TPodouble a, TPodouble b) 
 79 { 
 80     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); 
 81 } 
 82 
 83 int ISSAME(TPodouble  a, TPodouble  b) 
 84 { 
 85     if(fabs(a.x - b.x) > eps) return 0; 
 86     if(fabs(a.y - b.y) > eps) return 0; 
 87     return 1; 
 88 } 
 89 
 90 void between(TPodouble s1, TPodouble e1, TPodouble s2, TPodouble  e2) 
 91 { 
 92     double d1 = dis(s1, s2); 
 93     double d2 = dis(s1, e2); 
 94     double d3 = dis(e1, s2); 
 95     double d4 = dis(e1, e2); 
 96     double d5 = dis(s1, e1); 
 97     double d6 = dis(s2, e2); 
 98     if(ISSAME(s1, s2) && fabs(d5 + d6 - d4) < eps) printf("%.3lf %.3lf
", s1.x, s1.y); 
 99     else if(ISSAME(s1, e2) && fabs(d3 - d5 - d6) < eps) printf("%.3lf %.3lf
", s1.x, s1.y); 
100     else if(ISSAME(e1, s2) && fabs(d2 - d5 - d6) < eps) printf("%.3lf %.3lf
", s2.x, s2.y); 
101     else if(ISSAME(e1, e2) && fabs(d1 - d5 - d6) < eps) printf("%.3lf %.3lf
", e2.x, e2.y); 
102     else printf("Too much points in common
"); 
103 } 
104 
105 int main() 
106 { 
107     TPodouble s1, e1, s2, e2; 
108     TLine l1, l2; 
109     while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &s1.x, &s1.y, &e1.x, &e1.y, &s2.x, &s2.y, &e2.x, &e2.y) != EOF){ 
110         if(fabs((s1.y - e1.y) * (s2.x - e2.x) - (s1.x - e1.x) * (s2.y - e2.y)) < eps){ 
111             l1 = lineFromSegment(s1, e1); 
112             l2.c = -(l1.a * s2.x + l1.b * s2.y); 
113             if(fabs((l1.c - l2.c) / sqrt((double)l1.a * l1.a + l1.b * l1.b)) > 0){ 
114                 printf("No point in common
"); 
115             } 
116             else { 
117                 if(!isIntersected(s1, e1, s2, e2)) printf("No point in common
"); 
118                 else between(s1, e1, s2, e2); 
119             } 
120         } 
121         else { 
122             if(isIntersected(s1, e1, s2, e2)){ 
123                 l1 = lineFromSegment(s1, e1); 
124                 l2 = lineFromSegment(s2, e2); 
125                 Linedoubleer(l1, l2);     
126             } 
127             else printf("No point in common
"); 
128         }     
129     } 
130     return 0; 
131 }