3387519_tle.cc

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

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

int n;
int point[660][2];

double get(double ax, double ay, double bx, double by, double cx, double cy)
{
	double dx, dy, ex, ey, a1, a2, b1, b2, c1, c2, x, y;

	dx = (ax + cx) / 2.0; dy = (ay + cy) / 2.0;
	ex = (bx + cx) / 2.0; ey = (by + cy) / 2.0;
	a1 = cx - ax; b1 = cy - ay; c1 = dx * a1 + dy * b1;
	a2 = cx - bx; b2 = cy - by; c2 = ex * a2 + ey * b2;
	x = (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);
	y = (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1);
	return (x - ax) * (x - ax) + (y - ay) * (y - ay);
}

int main()
{
	int cas;
	int i, j, k;
	double ans, tmp;

	scanf("%d", &cas);
	while (cas-- > 0)
	{
		scanf("%d", &n);
		ans = 0.0;
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &point[i][0], &point[i][1]);
		}
		for (i = 0; i < n; i++)
		{
			for (j = i + 1; j < n; j++)
			{
				for (k = j + 1; k < n; k++)
				{
					tmp = get(point[i][0], point[i][1], point[j][0], point[j][1], point[k][0], point[k][1]);
					if (tmp > ans)
					{
						ans = tmp;
					}
				}
			}
		}
		printf("%.3lf\n", sqrt(ans));
	}
	return 0;
}