POJ 3301 Texas Trip （三分）

ACM

题目地址： 

题意： 

给定二维平面的n个点，要求一个面积最小的正方形，使其能覆盖全部的点。

分析： 

去求凸包你就输了... 

我们能够让正方形不要动。全部点进行旋转变换。这样结果是不会变形的。

 

变形即： x1=x*cos(a)-y*sin(a); y1=x*sin(a)+y*cos(a) 

本来想暴力看看的，后来发现是三分的，证明引用巨巨的：

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

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

代码：

/**  Author:      illuz 
     
      *  File:        3301.cpp*  Create Date: 2014-09-18 09:25:04*  Descripton:  triple*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           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;}