pku2921.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <cstdio>
#include <algorithm>
#include <cmath>
#define SIZE 10010
using namespace std;

typedef long long llong;
typedef struct Point
{
	int x, y;
}Point;

Point p[SIZE];
int N;
llong mul1, mul2;

int GCD(int a, int b)
{
	return b == 0 ? a : GCD(b, a % b);
}

bool cmp(const Point &a, const Point &b)
{
	mul1 = a.x;
	mul1 *= b.y;
	mul2 = b.x;
	mul2 *= a.y;
	return mul1 <= mul2;
}

int bsearch(const Point &x)
{
	int min, max, mid;
	min = 0;
	max = N;
	while (min + 1 < max)
	{
		mid = (min + max) / 2;
		if (cmp(x, p[mid]))
			max = mid;
		else
			min = mid; 
	}
	return min;
}

void init(int t)
{
	int i;
	int gcd, x, y;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &x, &y);
		gcd = GCD(x, y);
		x /= gcd;
		y /= gcd;
		if (y % 2 == 1)
		{
			x *= 2;
			y *= 2;
		}
		p[i].x= x;
		p[i].y= y;
	}
	sort(p, p + N, cmp);
	printf("Scenario #%d:\n", t);
}

double calcdis(Point &a, Point &b)
{
	double ang = fabs(1.0 * a.x / a.y - 1.0 * b.x / b.y);
	ang *= acos(-1.0);
	return 2.0 * N * sin(ang);
}

void solve()
{
	Point np;
	int i, pos;
	double tmp, max;
	max = 0;
	for (i = 0; i < N; i++)
	{
		np.y = p[i].y;
		np.x = (p[i].x + np.y / 2) % np.y;
		pos = bsearch(np);
		tmp = calcdis(p[i], p[pos]);
		if (tmp > max)
			max = tmp;
		tmp = calcdis(p[i], p[(pos+1)%N]);
		if (tmp > max)
			max = tmp;
	}
	printf("%.2lf\n\n", max);
}

int main()
{
	int t, T;
	scanf("%d", &T);
	for (t = 1; t <= T; t++)
	{
		init(t);
		solve();
	}
	return 0;
}