POJ-3301 Texas Trip 计算几何 三分

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;
    else
        return 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;
        else
            r = 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;
}