The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

PKU 3301 Texas Trip

枚举矩形的旋转角度,再将所有点转回来,然后用面积最小的与轴平行的正方形覆盖。
可以建立映射关系area=f(θ),f(θ)感觉上是凹函数,故三分。
#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
double const Pi=acos(-1.0);

#define eps 1e-8
int const maxn=31;
int n;
struct point 
{
    
double x,y;
}
p[maxn];

point rotate(point p,
double theta)//逆时针旋转theta度
{
    point ans;
    ans.x
=p.x*cos(theta)+p.y*sin(theta);
    ans.y
=-p.x*sin(theta)+p.y*cos(theta);
    
return ans;
}


double cal(double theta)
{
    point pp[maxn];
    
for(int i=0;i<n;i++)
        pp[i]
=rotate(p[i],-theta);
    
double minx=1000000000.0;
    
double maxx=-1000000000.0;
    
double miny=1000000000.0;
    
double maxy=-1000000000.0;
    
for(int i=0;i<n;i++)
    
{
        
if(pp[i].x<minx)
            minx
=pp[i].x;
        
if(pp[i].x>maxx)
            maxx
=pp[i].x;
        
if(pp[i].y<miny)
            miny
=pp[i].y;
        
if(pp[i].y>maxy)
            maxy
=pp[i].y;
    }

    
if((maxx-minx)>(maxy-miny))
        
return (maxx-minx)*(maxx-minx);
    
else
        
return (maxy-miny)*(maxy-miny);
}



int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
while(ca--)
    
{

        scanf(
"%d",&n);
        
for(int i=0;i<n;i++)
            scanf(
"%lf%lf",&p[i].x,&p[i].y);
        
double l=0;
        
double r=Pi;
        
while(l+eps<=r)
        
{
            
double mid=(l+r)/2;
            
double mmid=(mid+r)/2;
            
if(cal(mid)<cal(mmid))
                r
=mmid;
            
else
                l
=mid;
        }

        printf(
"%.2lf\n",cal(l));

    }


    
return 0;
}

posted on 2010-11-08 02:19 abilitytao 阅读(232) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理