首页 > 代码库 > POJ 3301 Texas Trip (三分)

POJ 3301 Texas Trip (三分)

POJ 3301 Texas Trip (三分)

ACM

题目地址: 
POJ 3301 Texas Trip

题意: 
给定二维平面的n个点,要求一个面积最小的正方形,使其能覆盖所有的点。

分析: 
去求凸包你就输了... 
我们可以让正方形不要动,所有点进行旋转变换,这样结果是不会变形的。 
变形即: x1=x*cos(a)-y*sin(a); y1=x*sin(a)+y*cos(a) 
本来想暴力看看的,后来发现是三分的,证明引用巨巨的:

可以证明它们都是凸性函数,故他们差的最大值也是凸性函数,故可以用三分法,对旋转角度进行三分,求出最小的满足要求的正方形,详细过程见代码。

交了几发,再次验证了:g++的double输出默认是用%f的。

代码

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  File:        3301.cpp
*  Create Date: 2014-09-18 09:25:04
*  Descripton:  triple
*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;

const int N = 31;
const double PI = acos(-1.0);
const double EPS = 1e-12;

int t, n;
double x[N], y[N];

inline double calc(double a) {
	double minx = 1000, miny = 1000, maxx = -1000, maxy = -1000;
	double xx, yy;
	repf (i, 1, n) {
		xx = x[i] * cos(a) - y[i] * sin(a);
		yy = x[i] * sin(a) + y[i] * cos(a);
		minx = min(minx, xx);
		maxx = max(maxx, xx);
		miny = min(miny, yy);
		maxy = max(maxy, yy);
	}
	return max(maxx - minx, maxy - miny);
}

int main() {
	ios_base::sync_with_stdio(0);

	double l, r, mid, mmid, ans;
	cin >> t;
	while (t--) {
		cin >> n;
		repf (i, 1, n) {
			cin >> x[i] >> y[i];
		}
		l = 0.0;
		r = PI;
		while (r - l > EPS) {
			mid = (l + r) / 2;
			mmid = (mid + r) / 2;
			ans = calc(mid);
			if (ans <= calc(mmid))
				r = mmid;
			else
				l = mid;
		}
		printf("%.2f\n", ans * ans);
		// brute force
//		ans = 1000;
//		for (double i = 0.0; i <= PI; i += 0.00005)
//			ans = min(ans, calc(i));
//		printf("%.2lf\n", ans * ans);
	}
	return 0;
}


POJ 3301 Texas Trip (三分)