线段重叠+投影

  1 #include <stdio.h>
  2 #include <math.h>
  3 #include <stdlib.h>
  4 
  5 #define eps 1e-8
  6 #define pi acos(-1)
  7 
  8 typedef struct SEG
  9 {
 10     double l, r;
 11 }SEG;
 12 
 13 typedef struct TPoint
 14 {
 15     double x, y;
 16 }TPoint; 
 17 
 18 typedef struct TLine
 19 {
 20     double a, b, c;
 21 }TLine;
 22 
 23 typedef struct Circle
 24 {
 25     TPoint c;
 26     double r;
 27 }Circle;
 28 
 29 double distance(double x1, double y1, double x2, double y2)
 30 {
 31     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
 32 }
 33 
 34 TPoint LineInter(TLine l1, TLine l2)
 35 {
 36     //求两直线得交点坐标
 37     TPoint tmp; 
 38     double a1 = l1.a;
 39     double b1 = l1.b;
 40     double c1 = l1.c;
 41     double a2 = l2.a;
 42     double b2 = l2.b;
 43     double c2 = l2.c;
 44     //注意这里b1 = 0 
 45     if(fabs(b1) < eps){
 46         tmp.x = -c1 / a1;  
 47         tmp.y = (-c2 - a2 * tmp.x) / b2;
 48     }       
 49     else{
 50         tmp.x = (c1 * b2 - b1 * c2) / (b1 * a2 - b2 * a1);
 51         tmp.y = (-c1 - a1 * tmp.x) / b1;
 52     }
 53     return tmp;
 54 }
 55 
 56 TLine lineFromSegment(TPoint p1, TPoint p2)
 57 {
 58     //线段所在直线,返回直线方程的三个系统 
 59     TLine tmp;
 60     tmp.a = p2.y - p1.y;
 61     tmp.b = p1.x - p2.x;
 62     tmp.c = p2.x * p1.y - p1.x * p2.y;
 63     return tmp;
 64 }
 65 
 66 int cmp(const void *a, const void *b)
 67 {
 68     SEG *c = (SEG *)a;
 69     SEG *d = (SEG *)b;
 70     if(c->l < d->l) return -1;
 71     else return 1;
 72 }
 73 
 74 int main()
 75 {
 76     int n, i, j;
 77     TPoint b, inter;
 78     double lbc, lcinter, a, bangle;
 79     double start, end;
 80     TLine l1;
 81     Circle circle[505];
 82     SEG seg[505];    
 83     
 84     while(scanf("%d", &n) && n){
 85         scanf("%lf%lf", &b.x, &b.y);
 86         for(i = 0;i < n;i++){
 87             scanf("%lf%lf%lf", &circle[i].c.x, &circle[i].c.y, &circle[i].r);
 88             if(fabs(b.x - circle[i].c.x) < eps) a = pi / 2;
 89             else a = atan((circle[i].c.y - b.y) / (circle[i].c.x - b.x));
 90             if(a < 0) a += pi;
 91             lbc = distance(b.x, b.y, circle[i].c.x, circle[i].c.y);
 92             bangle = asin(circle[i].r / lbc);
 93             l1 = lineFromSegment(b, circle[i].c);
 94             inter.x = -l1.c / l1.a;
 95             inter.y = 0.0;
 96             lcinter = distance(inter.x, inter.y, b.x, b.y);
 97             seg[i].l = inter.x - lcinter * circle[i].r / lbc / sin(a - bangle);
 98             seg[i].r = inter.x + lcinter * circle[i].r / lbc / sin(pi - a - bangle);            
 99         }
100         qsort(seg, n, sizeof(seg[0]), cmp);
101         start = seg[0].l;
102         end = seg[0].r;
103         for(i = 1;i < n;i++){
104             if(seg[i].l > end){
105                 printf("%.2lf %.2lf
", start, end);
106                 start = seg[i].l;
107                 end = seg[i].r;
108             }
109             else {
110                 if(seg[i].r > end) end = seg[i].r;
111             }
112         }
113         printf("%.2lf %.2lf

", start, end);
114     }
115     return 0;
116 }