Texas Trip
Problem's Link: http://poj.org/problem?id=3301
Mean:
给定n(n <= 30)个点，求出包含这些点的面积最小的正方形的面积。
analyse:
首先要确定的是旋转的角度在0到180度之间即可，超过180度是和前面的相同的。
坐标轴旋转后，坐标变换为：
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;
Time complexity: O(n)
Source code:
// Memory Time // 1347K 0MS // by : crazyacking // 2015-03-31-22.18 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; #define eps 1e-12 #define INF (1<<25) double ppx[40],ppy[40]; int n; double Cal(double a) { double xMin=INF*1.0,yMin=INF*1.0,xMax=-INF*1.0,yMax=-INF*1.0; for(int i=1;i<=n;i++) { double x1=ppx[i]*cos(a)-ppy[i]*sin(a); double y1=ppx[i]*sin(a)+ppy[i]*cos(a); if(x1>xMax) xMax=x1; if(x1<xMin) xMin=x1; if(y1>yMax) yMax=y1; if(y1<yMin) yMin=y1; } if(xMax-xMin<yMax-yMin) return yMax-yMin; else return xMax-xMin; } int main() { int t; int x,y; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); ppx[i]=x+500.0; ppy[i]=y+500.0; } double le=0,ri=PI,mid,mmid; double mid_va,mmid_va; while(le+eps<=ri) { mid=(le+ri)/2; mmid=(mid+ri)/2; mid_va=Cal(mid); mmid_va=Cal(mmid); if(mid_va<mmid_va) ri=mmid; else le=mid; } printf("%.2lf\n",Cal(le)*Cal(le)); } return 0; }
