UVA 12121 - You are around me ...（贪心+几何）

链接：12121 - You are around me ...

题意：给定n个人的坐标，椭圆的离心率e，椭圆的角度r。要求这n个人的椭圆面积相等，并且尽量大，但是不能有两两相交，问这个最大面积。

思路：贪心，先按x坐标排序算一次，再按y坐标排序算一次，每次椭圆和最近的两个椭圆相比计算出最大合适面积，维护这个面积的最小值即可。

代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const double INF = 1000000000;
const double pi = acos(-1.0);
const int N = 15005;
int n, i;
double e, r, x, y;


struct Point {
	double x, y;
	Point() {}
	Point(double _x, double _y) {
		x = _x; y = _y;
	}
} p[N];

bool cmpx(Point a, Point b) {
	return a.x < b.x;
}

bool cmpy(Point a, Point b) {
	return a.y < b.y;
}

double cal(Point a, Point b) {
	Point mid = Point((a.x + b.x) / 2, (a.y + b.y) / 2);
	double x = (mid.x - a.x) * (mid.x - a.x);
	double y = (mid.y - a.y) * (mid.y - a.y);
	double A = sqrt(fabs((x - e * e * x + y) / (1 - e * e)));
	return A * sqrt((A * A - A * A * e * e)) * pi;
}

double solve() {
	double ans = INF;
	sort(p, p + n, cmpx);
	for (i = 1; i < n; i++) {
		double t = cal(p[i - 1], p[i]);
		ans = min(ans, t);
	}
	sort(p, p + n, cmpy);
	for (i = 1; i < n; i++) {
		double t = cal(p[i - 1], p[i]);
		ans = min(ans, t);
	}
	return ans;
}

int main() {
	int cas = 0;
	while (~scanf("%d%lf%lf", &n, &e, &r) && n) {
		r = r * pi / 180;
		for (i = 0; i < n; i++) {
			scanf("%lf%lf", &x, &y);
			p[i] = Point(x * cos(r) + y * sin(r), -x * sin(r) + y * cos(r));
		}
		printf("Case %d:\n%.6lf\n", ++cas, solve());
	}
	return 0;
}