这题的大意是在整数坐标上，给定一些点，问说覆盖这些点的最小的正方形的面积，好像黑书上有道类似的，把正方形改成矩形，对于那道题的解法好像是，考虑到最后矩形至少会有一条边上有两个以上的点，所以枚举两个点，可能生成这个矩形，这样就把可能旋转的角度给离散化了，并且复杂度只有O(N^2)的，或者可能都有旋转卡壳的方法来解这个。但对于这道题，不知道这样离散可不可以，但想法都是把枚举数量减少下来，这里用到逼近迭代，就是先m分枚举范围，从中找到最小的，然后再在那个区间m分，这样迭代下去。
感谢：
http://hi.baidu.com/liugoodness/blog/item/1aaebb16494b314320a4e9ad.htmlhttp://hi.baidu.com/czyuan_acm/blog/item/8cc45b1f30cefefde1fe0b7e.html
代码 #include < iostream > #include < string > #include < vector > #include < map > #include < set > #include < queue > #include < math.h > using namespace std; const int MAX = 305 ; const double PI = asin( 1.0 ) * 2 ; const double EPS = 1e - 6 ; int n; double x[MAX]; double y[MAX]; double xx[MAX]; double yy[MAX]; double check( double a){ double minx = 1000000 ; double maxx = - minx; double miny = minx; double maxy = maxx; for ( int i = 0 ; i < n; i ++ ) { xx[i] = cos(a) * x[i] + sin(a) * y[i]; yy[i] = - sin(a) * x[i] + cos(a) * y[i]; minx = min(minx, xx[i]); maxx = max(maxx, xx[i]); miny = min(miny, yy[i]); maxy = max(maxy, yy[i]); } double e = (maxx - minx) > (maxy - miny) ? (maxx - minx) : (maxy - miny); return e * e;} double go(){ int m = 800 ; int times = 60 ; double begin = 0 ; double end = PI / 3 ; double res = - 1 ; double from; double a; double da; while (times -- ) { a = begin; da = (end - begin) / m; for ( int i = 0 ; i < m; i ++ ) { double t = check(a + da * i); if (res == - 1 || t < res) { res = t; from = a + da * i; } } begin = from - da; end = from + 2 * da; } return res;} int main(){ int T; scanf( " %d " , & T); while (T -- ) { scanf( " %d " , & n); for ( int i = 0 ; i < n; i ++ ) scanf( " %lf%lf " , & x[i], & y[i]); printf( " %.2lf\n " , go()); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/08/06/1793982.html
相关资源：数据结构—成绩单生成器