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 閱讀(321) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

PKU 3301 Texas Trip