1096.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1096 on 2006-01-09 at 15:55:41 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 512;
const double eps = 1e-4;
const double INF = 2e10;

class Pipe {
public:
	double cx, cy, cr;
	double l, r;
	void make(double, double);
	bool operator <(const Pipe&) const;
};
void Pipe::make(double x, double y) {
	scanf("%lf %lf %lf", &cx, &cy, &cr);
	double d = (x-cx)*(x-cx)+(y-cy)*(y-cy);
	double alpha = (x-cx)/(y-cy), beta = cr/sqrt(d-cr*cr);
	l = x - y * (alpha+beta)/(1-alpha*beta), r = x - y * (alpha-beta)/(1+alpha*beta);
	if(l > r) swap(l, r);
}
bool Pipe::operator <(const Pipe& p) const {
	if(fabs(l-p.l) > eps) return l < p.l;
	else return r < p.r;
}

int main()
{
	int n, x, y, i;
	Pipe pipe[MAX];

	while(scanf("%d", &n) != EOF && n != 0) {
		scanf("%d %d", &x, &y);
		for(i = 0; i < n; i++) pipe[i].make(x, y);
		pipe[n].l = pipe[n].r = INF; n++;
		sort(pipe, pipe+n);
		double pl = pipe[0].l, pr = pipe[0].r;
		for(i = 1; i < n; i++) {
			if(pipe[i].l - pr < eps) pr = max(pr, pipe[i].r);
			else printf("%.2lf %.2lf\n", pl, pr), pl = pipe[i].l, pr = pipe[i].r;
		}
		putchar('\n');
	}
	
	return 0;
}