POJ 3301 Texas Trip
题目大意:
在二维坐标系中给出一些点。求能覆盖他们的最小正方形的面积(正方形的边不一定平行坐标轴)
解题思路:
对于一个点。若坐标轴旋转a度(弧度制)。那么X‘=X*cos(a)-Y*sin(a);Y'=Y*cos(a)+X*sin(a);
对于角度三分,对于正方形面积是个单峰函数在【0。pi】。
有最小值。
以下是代码:
#include <set> #include <map> #include <queue> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #define eps 1e-8 #define pi acos(-1.0) #define inf 107374182 #define inf64 1152921504606846976 #define lc l,m,tr<<1 #define rc m + 1,r,tr<<1|1 #define iabs(x) ((x) > 0 ? (x) : -(x)) #define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (SIZE)) #define clearall(A, X) memset(A, X, sizeof(A)) #define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE)) #define memcopyall(A, X) memcpy(A , X ,sizeof(X)) #define max( x, y ) ( ((x) > (y)) ?(x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; struct node { double x,y; }point[305]; int n; double does(double a) { double maxx=-10000000,maxy=-100000000,minx=100000000,miny=100000000,tx,ty; for(int i=0;i<n;i++) { tx=point[i].x*cos(a)-point[i].y*sin(a); ty=point[i].y*cos(a)+point[i].x*sin(a); maxx=max(maxx,tx); maxy=max(maxy,ty); minx=min(minx,tx); miny=min(miny,ty); } return max(maxx-minx,maxy-miny); } int main() { int T; double l,r,lmid,rmid,ans1,ans2; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%lf%lf",&point[i].x,&point[i].y); } l=0.0; r=pi; while(r-l>eps) { lmid=(l+r)/2; rmid=(lmid+r)/2; ans1=does(lmid); ans2=does(rmid); if(ans1<=ans2)r=rmid; else l=lmid; } printf("%.2lf\n",ans1*ans1); } return 0; }
相关文章
- poj 2456 Aggressive cows 贪心+二分
- POJ 2955 Brackets 区间DP
- poj 1905Expanding Rods
- POJ - 1700 Crossing River
- 【POJ 3026】Borg Maze
- POJ题目1947 Rebuilding Roads(树形dp)
- poj(1011)——Sticks(经典的dfs+剪枝)
- POJ 3041(最小点覆盖)
- POJ 1160 Post Office (动态规划)
- poj 3311 状压DP
- POJ - 3249 Test for Job (DAG+topsort)
- poj 1699 Best Sequence(AC自己主动机+如压力DP)
- POJ 1631 Bridging signals(LIS 二分法 高速方法)
- POJ 1066 Treasure Hunt(相交线段&&更改)
- poj 1147 Binary codes
- poj 1328 Radar Installation
- POJ_1195 Mobile phones 【二维树状数组】
- POJ 2567 Code the Tree & POJ 2568 Decode the Tree Prufer序列
- POJ 3169 Layout(差分约束啊)