POJ 3737 - UmBasketella

题面 ：给定一个圆锥的表面积（包括下底），求最大的体积和该条件下的半径和高

题解 ：三分半径，当半径等于0的时候为下限，当母线等于r的时候为上限。易得出半径的范围（0，sqrt(s/(2*pi)）)。由 S = pi * r * (r + l) 易得出 l = (s - pi * r^2) / (pi * r) , h = sqrt(l^2- r^2) ,所以 v =(pi * r^2 * h) / 3。

#include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<iostream> #include<cstring> #include<string> #include<cmath> using namespace std; const double pi = acos((double)(-1)); #define inf 0x3f3f3f3f #define ll long long const int maxn = 20010; const int mod = 1e9 + 7; double s, v, r , h,l; double f(double radius){ l = (s - pi*radius*radius)/(pi*radius); h = sqrt(l*l - radius*radius); v = (h*pi*radius*radius)/3.0; r = radius; return v; } double sanfen(){ double right , left ,midl, midr; left = 0; right = sqrt(s/(2*pi)); while(right - left > 1e-6){ midl = left + (right - left)/3; midr = right - (right - left)/3; if(f(midl) > f(midr)) right = midr; else left = midl; } return f(left); } int main(){ while(~scanf("%lf",&s)){ printf("%.2f\n",sanfen()); printf("%.2f\n%.2f\n",h,r); } return 0; }

POJ 3301 - Texas Trip

题意 ：给出二维坐标上的n个点，要求找到一个正方形使它覆盖所有点并且面积最小。

题解 ：旋转坐标系，三分旋转角度（看了大佬的博客才知道的）。从0旋转到180度 ，寻找横向的最长距离和纵向的最长距离，取这两个的最大值作为正方形的边长。旋转后的坐标有对应的公式： X’ = x * cos(angle) - y * sin(angle) Y’ = y * cos(angle) + x * sin(angle)

#include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<iostream> #include<cstring> #include<string> #include<cmath> using namespace std; const double pi = acos((double)(-1)); #define inf 0x3f3f3f3f #define ll long long #define eps 1e-9 const int maxn = 20010; const int mod = 1e9 + 7; int t, n; double l,r,midl,midr; struct Point{ double x,y; }p[35]; double f(double angle){ double maxx = -inf , minx = inf , maxy = -inf, miny = inf; for(int i = 1;i <= n ;i++){ double _x = p[i].x*cos(angle) - p[i].y*sin(angle); double _y = p[i].y*cos(angle) + p[i].x*sin(angle); maxx = max(maxx, _x); minx = min(minx, _x); maxy = max(maxy, _y); miny = min(miny, _y); } double a = max(maxx - minx, maxy - miny); return a*a; } double sanfen(){ l = 0,r = 180; while(r - l > eps){ midl = l + (r - l)/3; midr = r - (r - l)/3; if(f(midl) > f(midr)) l = midl; else r = midr; } return f(r); } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } printf("%.2f\n",sanfen()); } return 0; }