1024.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1024 on 2006-02-11 at 21:14:58 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 16;
const double SQRT_3 = sqrt(3.0);
const double INF = 1e10;

class Tooth {
public:
	int tn;
	double rx, ry, side[MAX];
	double tpx[MAX], end[MAX], th[MAX];
	void make(bool);
	double height(double) const;
	double move(double, double, bool) const;
	inline double tpy(int i) const { return fabs(ry) > 1e-3 ? ry-th[i] : th[i]; }
};
void Tooth::make(bool refer) {
	if(refer) scanf("%lf %lf", &rx, &ry);
	else rx = ry = 0;
	int i;
	end[0] = rx; scanf("%d", &tn);
	for(i = 0; i < tn; i++) {
		scanf("%lf", &side[i]); 
		end[i+1] = side[i] + end[i];
		tpx[i] = end[i+1] - side[i] / 2;
		th[i] = side[i] * SQRT_3 / 2;
	}
}
double Tooth::height(double x) const {
	if(x < rx || x > end[tn-1]) return -INF;
	int p; x -= rx;
	for(p = 0; x >= side[p]; p++) x -= side[p];
	return min(x, side[p]-x)*SQRT_3;
}
double Tooth::move(double x, double y, bool left) const {
	double dx = (ry - y)/SQRT_3, mx = x + (left ? dx : -dx);
	int p = upper_bound(end, end+tn+1, mx) - end - 1;
	if(left == (dx < 0) && fabs(end[p]-mx) > 1e-3) p++;
	if(p <= 0 || p >= tn) return INF;
	return 2*fabs(dx) - fabs(end[p]-mx);
}

int main()
{
	int i, j, case_no, T;
	Tooth t[2];

	scanf("%d", &T);
	for(case_no = 0; case_no < T; case_no++) {
		t[1].make(false); t[0].make(true);
		if(t[0].tpx[0] >= t[1].tpx[t[1].tn-1]) printf("MW\n");
		else if(t[0].tpx[t[0].tn-1] <= t[1].tpx[0]) printf("WM\n");
		else {
			double h = INF, l = INF, r = INF;
			for(i = 0; i < 2; i++)
				for(j = 0; j < t[i].tn; j++)
					h = min(h, t[0].ry-t[i].th[j]-t[1-i].height(t[i].tpx[j]));
			t[0].ry -= h;
			for(i = 0; i < 2; i++)
				for(j = 0; j < t[i].tn; j++) {
					l = min(l, t[1-i].move(t[i].tpx[j], t[i].tpy(j), true));
					r = min(r, t[1-i].move(t[i].tpx[j], t[i].tpy(j), false));
				}
			t[0].ry -= (l+r)*SQRT_3/2; t[0].rx += (r-l)/2;
			printf("%.3lf %.3lf\n", t[0].rx, t[0].ry);
		}
	}
	
	return 0;
}