1774.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1774 on 2006-04-21 at 22:10:23 */ 
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int W = 1000, H = 1000;
const int SN = 1024;
const int WEST = 10000, EAST = 10001;
const double eps = 1e-4;

class Snake {
public:
	int o;
	double x, y, r;
	bool vst;
	vector<int> n;
	void clear() { vst = false; n.clear(); }
	void make();
	void add(Snake&);
	bool ins(const Snake&) const;
	double posY(double) const;
};
void Snake::make() {
	clear();
	scanf("%lf %lf %lf", &x, &y, &r);
	if(x < r) n.push_back(WEST);
	if(W-x < r) n.push_back(EAST);
}
void Snake::add(Snake& s) {
	n.push_back(s.o);
	s.n.push_back(o);
}
bool Snake::ins(const Snake& s) const {
	switch(s.o) {
	case 0: return H-y < r;
	case 1: return y < r;
	default: return (x-s.x)*(x-s.x)+(y-s.y)*(y-s.y) < (r+s.r)*(r+s.r);
	}
}
double Snake::posY(double px) const {
	double d = fabs(x-px);
	return y-sqrt(r*r-d*d);
}

int main()
{
	Snake snake[SN];
	int n, i, j;

	for(i = 0; i < SN; i++) snake[i].o = i;
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < 2; i++) snake[i].clear();
		for(i = 2; i < n+2; i++) {
			snake[i].make();
			for(j = 0; j < i; j++)
				if(snake[i].ins(snake[j])) snake[i].add(snake[j]);
		}
		int stack[SN], top = 0;
		double y[2] = { H, H };
		stack[top++] = 0; snake[0].vst = true;
		while(top > 0) {
			int p = stack[--top];
			for(i = 0; i < (int)snake[p].n.size(); i++) {
				int o = snake[p].n[i];
				if(o == WEST) y[0] = min(y[0], snake[p].posY(0));
				else if(o == EAST) y[1] = min(y[1], snake[p].posY(W));
				else if(!snake[o].vst) { snake[o].vst = true; stack[top++] = o; }
			}
		}
		if(snake[1].vst) printf("Bill will be bitten.\n");
		else printf("Bill enters at (0.00, %.2lf) and leaves at (1000.00, %.2lf).\n", y[0], y[1]);
	}
	
	return 0;
}