首页 > 代码库 > POJ1375 Intervals(直线与圆切线、线段合并)

POJ1375 Intervals(直线与圆切线、线段合并)

题目链接:

  http://poj.org/problem?id=1375

题目描述:

Intervals
 

Description

In the ceiling in the basement of a newly open developers building a light source has been installed. Unfortunately, the material used to cover the floor is very sensitive to light. It turned out that its expected life time is decreasing dramatically. To avoid this, authorities have decided to protect light sensitive areas from strong light by covering them. The solution was not very easy because, as it is common, in the basement there are different pipelines under the ceiling and the authorities want to install the covers just on those parts of the floor that are not shielded from the light by pipes. To cope with the situation, the first decision was to simplify the real situation and, instead of solving the problem in 3D space, to construct a 2D model first. 
Within this model, the x-axis has been aligned with the level of the floor. The light is considered to be a point light source with integer co-ordinates [bx,by]. The pipes are represented by circles. The center of the circle i has the integer co-ordinates [cxi,cyi] and an integer radius ri. As pipes are made from solid material, circles cannot overlap. Pipes cannot reflect the light and the light cannot go through the pipes. You have to write a program which will determine the non-overlapping intervals on the x-axis where there is, due to the pipes, no light from the light source. 
技术分享

Input

The input consists of blocks of lines, each of which except the last describes one situation in the basement. The first line of each block contains a positive integer number N < 500 expressing the number of pipes. The second line of the block contains two integers bx and by separated by one space. Each of the next N lines of the block contains integers cxi, cyi and ri, where cyi + ri < by. Integers in individual lines are separated by one space. The last block consists of one line containing n = 0.

Output

The output consists of blocks of lines, corresponding to the blocks in the input(except the last one). One empty line must be put after each block in the output. Each of the individual lines of the blocks in the output will contain two real numbers, the endpoints of the interval where there is no light from the given point light source. The reals are exact to two decimal places and separated by one space. The intervals are sorted according to increasing x-coordinate.

Sample Input

6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
1
300 300
300 150 90
1
300 300
390 150 90
0

Sample Output

0.72 78.86
88.50 133.94
181.04 549.93

75.00 525.00

300.00 862.50

 

题目大意:

  给一个灯泡和一堆圆(保证灯泡纵坐标最大),求影子的位置

思路:

  算出过b点与各个圆的切线,求出与x轴交点,然后组成一个线段

  然后对求得的线段组进行合并

 

代码:

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <vector>
  7 using namespace std;
  8 
  9 const double EPS = 1e-10;        //精度系数
 10 const double PI = acos(-1.0);    //π
 11 const int N = 510;
 12 
 13 struct Point {
 14     double x, y;
 15     Point(double x = 0, double y = 0) :x(x), y(y) {}
 16 };    //点的定义
 17 
 18 typedef Point Vector;    //向量的定义
 19 
 20 Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }    //向量减法
 21 
 22 int dcmp(double x) {
 23     if (fabs(x) < EPS)return 0; else return x < 0 ? -1 : 1;
 24 }    //与0的关系
 25 
 26 double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }    //向量点乘
 27 double Length(Vector A) { return sqrt(Dot(A, A)); }    //向量长度
 28 
 29 Vector Rotate(Vector A, double rad) {
 30     return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad));
 31 }    //逆时针旋转rad度
 32 
 33 struct Circle {
 34     Point c;
 35     double r;
 36     Circle() :c(Point(0, 0)), r(0) {}
 37     Circle(Point c, double r = 0) :c(c), r(r) {}
 38     Point point(double a) { return Point(c.x + cos(a)*r, c.y + sin(a)*r); }    //输入极角返回点坐标
 39 }C[N];    //
 40 
 41 int getTangents(Point p, Circle C, Vector* v) {
 42     Vector u = C.c - p;
 43     double dist = Length(u);
 44     if (dist < C.r)return 0;
 45     else if (dcmp(dist - C.r) == 0) {    //p在圆上,只有一条切线
 46         v[0] = Rotate(u, PI / 2);
 47         return 1;
 48     } else {
 49         double ang = asin(C.r / dist);
 50         v[0] = Rotate(u, -ang);
 51         v[1] = Rotate(u, +ang);
 52         return 2;
 53     }
 54 }    //过点p到圆C的切线。v[i]是第i条切线的向量。返回切线条数
 55 
 56 double LineInterX_axisPoint(Point p, Vector v) {
 57     double t = -1 * p.y / v.y;
 58     return p.x + t*v.x;
 59 }    //直线与x轴交点横坐标
 60 
 61 struct Interval {
 62     double l, r;
 63     Interval(double l = 0, double r = 0) :l(l), r(r) {}
 64     const bool operator < (Interval A) const {
 65         return l < A.l;
 66     }
 67 };
 68 
 69 void CombineIntervals(vector<Interval>& itvls) {
 70     int n = itvls.size();
 71     if (!n)return;
 72     sort(itvls.begin(), itvls.end());
 73     vector<Interval> ans;
 74     double nl = itvls[0].l, nr = itvls[0].r;
 75     for (int i = 1; i < n; ++i) {
 76         double tl = itvls[i].l, tr = itvls[i].r;
 77         if (dcmp(tl - nr) > 0) {
 78             ans.push_back(Interval(nl, nr));
 79             nl = tl, nr = tr;
 80         } else nr = max(tr, nr);
 81     }
 82     ans.push_back(Interval(nl, nr));
 83     itvls.clear();
 84     for (int i = 0; i < (int)ans.size(); ++i)
 85         itvls.push_back(ans[i]);
 86 }    //合并线段
 87 
 88 int n;
 89 
 90 int main() {
 91     while (cin >> n && n) {
 92         int bx, by, a, b, R;
 93         scanf("%d%d", &bx, &by);
 94         for (int i = 0; i < n; ++i) {
 95             scanf("%d%d%d", &a, &b, &R);
 96             C[i].c.x = a, C[i].c.y = b, C[i].r = R;
 97         }
 98         Point B(bx, by);
 99         Vector v[2];
100         vector<Interval> itvls;
101         double l, r;
102         for (int i = 0; i < n; ++i) {
103             getTangents(B, C[i], v);
104             l = LineInterX_axisPoint(B, v[0]), r = LineInterX_axisPoint(B, v[1]);
105             if (l > r)swap(l, r);
106             itvls.push_back(Interval(l, r));
107         }
108         CombineIntervals(itvls);
109         for (int i = 0; i < (int)itvls.size(); ++i)
110             printf("%.2lf %.2lf\n", itvls[i].l, itvls[i].r);
111         printf("\n");
112     }
113 }

 

POJ1375 Intervals(直线与圆切线、线段合并)