2826588_ac_46ms_100k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define PI acos(-1)

using namespace std;

struct point
{
	double x, y;
};

struct segment
{
	double l, r;
};

segment seg[1000];
int no;

struct line
{
	double a, b, c;//ax+by+c=0;
};

struct circle
{
	point c;//圆心
	double r;//半径
};

double distance(point a,point b)//两点距离公式
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

line LineFromSeg(point a,point b)
{
	line l;

	l.a = b.y - a.y;
    l.b = a.x - b.x;
    l.c = b.x * a.y - a.x * b.y;
	return l;
}

bool cmp(segment a,segment b)
{
	return a.l < b.l;
}

int main()
{
	double left, right;
	int i, j, n;
	point light, tmp;
	circle pipe;
	line l;
	double angle, dis, beta, len;

	while(scanf("%d",&n)==1&&n)
	{
		no = 0;
		scanf("%lf%lf",&light.x,&light.y);
		while(n--)
		{
			scanf("%lf%lf%lf",&pipe.c.x,&pipe.c.y,&pipe.r);
			if(pipe.c.x==light.x)
				angle = PI/2;
			else
				angle = atan((pipe.c.y-light.y)/(pipe.c.x-light.x));
			if(angle < 0)
				angle += PI;
			dis = distance(pipe.c,light);
			beta = asin(pipe.r/dis);
			l = LineFromSeg(pipe.c,light);
			tmp.y = 0;tmp.x = -l.c/l.a;
			len = distance(light,tmp);
			seg[no].l = tmp.x - len * pipe.r / dis / sin(angle - beta);
			seg[no].r = tmp.x + len * pipe.r / dis / sin(PI - angle - beta);
			no++;
		}
		sort(seg,seg+no,cmp);
		for(i = 0; i < no; i++)
		{
			left = seg[i].l,right = seg[i].r;
			j = i;
			while(j<no&&seg[j].l<=right)
			{
				if(seg[j].r>right)
					right = seg[j].r;
				j++;
			}
			printf("%.2lf %.2lf\n",left,right);
			i = j-1;
		}
		printf("\n");
	}
	return 0;
}