2068883_ac_46ms_32k.c

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

# include <stdio.h>
# include <math.h>

struct node
{
	int x;
	int y;
	int r;
}bebal[1000];

void input()
{
	int i, j, n, mark, p;
	double x1, x2, x, y1, y2, y, r1, r2, tmp;

	while(scanf("%d",&n)==1&&n)
	{
		for(i = 0; i < n; i++)
			scanf("%d%d%d",&bebal[i].x,&bebal[i].y,&bebal[i].r);
		
		for(j = 1; j < n; j++){
		x2 = y2 = 0;r2 = 0;mark = 0;
		for(i = j-1; i >= 0; i--)
		{
			r1 = bebal[i+1].r*bebal[i+1].r;
			tmp = r1+r2;
			x1 = bebal[i+1].x;y1 = bebal[i+1].y;
			x = (r1*x1+r2*x2)/tmp;
			y = (r1*y1+r2*y2)/tmp;
			r2 = tmp;
			x2 = x; y2 = y;
			if((x-bebal[i].x)*(x-bebal[i].x)+(y-bebal[i].y)*(y-bebal[i].y)-bebal[i].r*bebal[i].r>=0)
			{
				mark = 1;
				p = j;
				goto ed;
			}
		}
		}
ed :
		if(!mark)
			printf("Feasible \n");
		else
			printf("Unfeasible %d\n",p);
	}
}

int main()
{
	input();
	return 1;
}