2309.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2309 on 2006-08-07 at 19:04:05 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int KN = 10240;

class Knight {
public:
	double ang;
	void make() { int p, q; scanf("%d %d", &p, &q); ang = 2*M_PI*p/q; }
	double dis(const Knight&) const;
};
double Knight::dis(const Knight& k) const {
	double da = abs(ang-k.ang)/2;
	return 2*sin(da);
}

int main()
{
	Knight k[KN];
	int n, i, t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		for(i = 0; i < n; i++) k[i].make();
		int e = 0;
		double dis = 0;
		for(i = 0; i < n; i++) {
			double td = -1;
			while(true) {
				double nd = k[i].dis(k[e]);
				if(nd > td) { td = nd; e = (e+1)%n; }
				else break;
			}
			dis = max(dis, td); e = (e+n-1)%n;
		}
		printf("Scenario #%d:\n%.2lf\n\n", t+1, n*dis);
	}
	
	return 0;
}