poj3301Texas Trip [三分]

Description

给出n个点的坐标，求一个最小的正方形可以覆盖所有点。

Input

第一行一个正整数T，表示数据的组数。
每组数据第一行一个整数n，表示点的个数。
接下来n行，每行两个整数表示坐标。
T = 30, n = 30, 坐标的绝对值=500

Output

每组数据一行一个两位小数表示正方形面积。

Sample Input

2
4
-1 -1
1 -1
1 1
-1 1
4
10 1
10 -1
-10 1
-10 -1

Sample Output

4.00
242.00

Solution

每次把所有点旋转一个角度，看这时的正方形面积。
三分角度即可。
唉一开始eps设的1e-6结果WA了一万发。

#include cstdio
#include cstring
#include algorithm
#include iostream
#include cmath

using namespace std;

const double pi = acos(-1.0);
const double eps = 1e-8;
const double INF = 1000000;

struct Point{
    double x, y;
};

int T, n;
Point p[35];

double cal(double phi) {
    double maxx = -INF, maxy = -INF;
    double minx = INF, miny = INF;
    for (int i = 0; i  n; i++) {
        double x = p[i].x * cos(phi) - p[i].y * sin(phi);
        double y = p[i].x * sin(phi) + p[i].y * cos(phi);
        maxx = max(maxx, x);
        maxy = max(maxy, y);
        minx = min(minx, x);
        miny = min(miny, y);
    }
    return max((maxx - minx) * (maxx - minx), (maxy - miny) * (maxy - miny));
}

int main() {
    // freopen("3301.in", "r", stdin);
    scanf("%d", T);
    while (T--) {
        scanf("%d", n);
        for (int i = 0; i  n; i++)
            scanf("%lf %lf", p[i].x, p[i].y);
        double l = 0.0, r = pi / 2;
        while (l + eps  r) {
            double m1 = l + (r - l) / 3.0;
            double m2 = r - (r - l) / 3.0;
            double v1 = cal(m1);
            double v2 = cal(m2);
            if (v1  v2) r = m2;
            else l = m1;
        }
        printf("%.2lf\n", cal(l));;
    }
    return 0;
}