POJ-3301 Texas Trip
题意： 求最大正方形覆盖
分析： 旋转所有的点， 统计最大和最小的x，y坐标。这是一个凹函数（好像是的吧）， 然后三分旋转区间， 求解。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;const int MAXN = 555;const double eps = 1e-12;
const double pi = acos(-1);
const double inf = 0x3f3f3f3f;int sgn(double x)
{if (fabs(x) < eps)return 0;if (x < 0)return -1;elsereturn 1;
}
struct Point
{double x, y;Point() {}Point(double _x, double _y){x = _x;y = _y;}Point operator+(const Point b) const{return Point(x + b.x, y + b.y);}Point operator-(const Point b) const{return Point(x - b.x, y - b.y);}double operator*(const Point b) const{return x * b.x + y * b.y;}double operator^(const Point b) const{return x * b.y - y * b.x;}Point rotright(Point p, double angle){Point v = (*this) - p;double c = cos(angle), s = sin(angle);return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);}
};Point p[MAXN];
int n;double getArea(double angle)
{double x1 = inf, x2 = -inf, y1 = inf, y2 = -inf;for (int i = 0; i < n; i++){Point pp = p[i].rotright(Point(0, 0), angle);x1 = min(x1, pp.x);x2 = max(x2, pp.x);y1 = min(y1, pp.y);y2 = max(y2, pp.y);}double t = max(x2 - x1, y2 - y1);return t * t;
}
double solve()
{double l, r, mid, midmid;l = 0, r = pi / 2;double ans = getArea(0);while (r - l > eps){mid = (l + r) / 2;midmid = (mid + r) / 2;double area1 = getArea(mid);double area2 = getArea(midmid);if (area1 > area2)l = mid;elser = midmid;}ans = min(ans, getArea(l));return ans;
}
int main()
{int T;scanf("%d", &T);while (T--){scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%lf%lf", &p[i].x, &p[i].y);}printf("%.2f\n", solve());}return 0;
}