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 阅读(310) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理