三分法。
其实一开始我是二分做的，二分的对象是正方形的边长，判断可行行则是将整幅图每次旋转一个微小角度，计算与坐标轴平行覆盖所有点的最小正方形。虽然这题精度和数据规模都一般，但还是妥妥的TLE了。于是看了讨论，又参考了这篇文章。
思路还是很清晰的，旋转范围是[0,pi/2]，在这范围内最短边长值是凹函数。于是对角度三分之后，计算所有点坐标中x、y两方向上的最大差值，并取较大值为此时正方形边长。迭代直到精度足够即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n; double r[30],a[30]; const double eps=1e-8; const double ma=3.141592653589793/2; void init() { int i; double x,y; for(i=0;i<n;i++) { scanf("%lf%lf",&x,&y); r[i]=sqrt(x*x+y*y); a[i]=asin(y/r[i]); if(x<0) { if(y>0) a[i]=ma*2-a[i]; else a[i]=-ma*2-a[i]; } } } double calc(double m) { int i; double x,y,lx,rx,by,ty; lx=by=1e30; rx=ty=-1e30; for(i=0;i<n;i++) { x=r[i]*cos(a[i]+m); y=r[i]*sin(a[i]+m); lx=min(lx,x); rx=max(rx,x); by=min(by,y); ty=max(ty,y); } return max(rx-lx,ty-by); } void solve() { double l,h,m,mm,e,ee; for(l=0,h=ma;l<h-eps;) { m=(l+h)/2; mm=(m+h)/2; e=calc(m); ee=calc(mm); if(e<ee) h=mm; else l=m; } e=calc(l); printf("%.2f\n",e*e); } int main() { scanf("%*d"); while(~scanf("%d",&n)) { init(); solve(); } return 0; } |
又学到了很实用的算法。 ^ ^