POJ 1375 圆外一点引向圆的切线，直线交点

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

Output

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

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/4/20 9:39:31
File Name :8.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
	if(fabs(x)<eps)return 0;
	return x>0?1:-1;
}
struct Point{
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;y=_y;
	}
};
Point operator + (Point a,Point b){
	return Point(a.x+b.x,a.y+b.y);
}
Point operator - (Point a,Point b){
	return Point(a.x-b.x,a.y-b.y);
}
Point operator * (Point a,double p){
	return Point(a.x*p,a.y*p);
}
Point operator / (Point a,double p){
	return Point(a.x/p,a.y/p);
}
bool operator < (const Point &a,const Point &b){
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){
	return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point a,Point b){
	return a.x*b.x+a.y*b.y;
}
double Length(Point a){
	return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
	return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
	return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
	return a.x*b.y-a.y*b.x;
}
Point vecunit(Point x){
	return x/Length(x);
}
Point Normal(Point x){
	return Point(-x.y,x.x);
}
Point Rotate(Point a,double rad){
	return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
struct Line{
	Point p,v;
	double ang;
	Line(){}
	Line(Point P,Point v):p(P),v(v){
		ang=atan2(v.y,v.x);
	}
	bool operator < (const Line &L) const {
		return ang<L.ang;
	}
	Point point(double a){
		return p+(v*a);
	}
};
struct Circle{
	Point c;
	double r;
	Circle(){}
	Circle(Point c,double r):c(c),r(r){}
	Point point(double a){
		return Point(c.x+cos(a)*r,c.y+sin(a)*r);
	}
};
int getTangents(Point p,Circle C,Point *v){
	Point u=C.c-p;
	double dist=Length(u);
	if(dist<C.r)return 0;
	else if(dcmp(dist-C.r)==0){
		v[0]=Rotate(u,pi/2);
		return 1;
	}
	double ang=asin(C.r/dist);
	v[0]=Rotate(u,-ang);
	v[1]=Rotate(u,ang);
	return 2;
}
Point GetLineIntersection(Point p,Point v,Point q,Point w){
	Point u=p-q;
	double t=Cross(w,u)/Cross(v,w);
	return p+v*t;
}
struct PP{
	double l,r;
}pp[100000];
bool cmp(PP a,PP b){
	return a.l<b.l;
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n;
	 while(cin>>n&&n){
		 Point p,v[10];Circle q;
		 scanf("%lf%lf",&p.x,&p.y);
		 for(int i=0;i<n;i++){
			 scanf("%lf%lf%lf",&q.c.x,&q.c.y,&q.r);
			 getTangents(p,q,v);
			 pp[i].l=GetLineIntersection(p,v[0],Point(-INF,0),Point(1,0)).x;
			 pp[i].r=GetLineIntersection(p,v[1],Point(-INF,0),Point(1,0)).x;
			 if(pp[i].l>pp[i].r)swap(pp[i].l,pp[i].r);
		 }
		 sort(pp,pp+n,cmp);
		// cout<<"han: "<<endl;
		// for(int i=0;i<n;i++)cout<<pp[i].l<<" "<<pp[i].r<<endl;
		 double L=pp[0].l,R=pp[0].r;
		 for(int i=1;i<n;i++){
			 if(pp[i].l>R){
				 printf("%.2f %.2f\n",L,R);
				 L=pp[i].l,R=pp[i].r;
			 }
			 else R=max(R,pp[i].r);
		 }
		 printf("%.2f %.2f\n\n",L,R);
	 }
     return 0;
}

POJ 1375 圆外一点引向圆的切线，直线交点,布布扣,bubuko.com

POJ 1375 圆外一点引向圆的切线，直线交点

原文：http://blog.csdn.net/xianxingwuguan1/article/details/24176265