题目地址:http://poj.org/problem?id=3301

简述:T组测试数据,每组线输入n,代表有n个点,接下来输入这n个点的坐标,坐标都是整数。

要求用一个最小的正方形覆盖所有的点,输出它的面积,精确到小数点后两位。

算法思路:枚举角度,计算面积, 三分枚举

(可参考:程序设计 解题策略  吴永辉...著 394页)

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <iostream>
#include <string>
#include <algorithm>
#define eps 1e-9 using namespace std; int tg, n;
int x[1000], y[1000]; double calc(double d)
{
int i, j;
double dis1,dis2,dis;
dis=0.0; for(i=1; i<n; i++)
{
for(j=i+1; j<=n; j++)
{
dis1=fabs( cos(d)*(y[i]-y[j])-sin(d)*(x[i]-x[j]) );
dis2=fabs( sin(d)*(y[i]-y[j])+cos(d)*(x[i]-x[j]) );
if(dis < dis1 ) dis = dis1;
if(dis < dis2 ) dis = dis2;
}
}
return (dis*dis);
} int main()
{
double ll, rr, mid, midmid;
double s1, s2; cin>>tg;
while(tg--)
{
cin>>n;
for(int i=1; i<=n; i++){
cin>>x[i]>>y[i];
} ll=0.0; rr=acos(-1.0); //rr=180.0 确定好区间
while( rr-ll>=eps )
{
mid = (ll+rr)/2; midmid=(rr+mid)/2; s1=calc(mid);
s2=calc(midmid);
if(s1<s2){
rr=midmid;
}else
{
ll=mid;
}
}
printf("%0.2lf\n", s1<s2?s1:s2);
}
return 0;
}

最新文章

  1. &quot;bower.json 中出现语法错误&quot; 的解决方案之一
  2. 深入理解javascript原型和闭包(11)——执行上下文栈
  3. 【node】使用gulp来维护网站项目
  4. 编译libjpeg库
  5. MySQL索引的创建、删除和查看
  6. 基于mjpg_streamer视频服务器移植【转】
  7. U3D刚体测试1-刚体非刚体物体非Kinematic等之间的碰撞关系
  8. 转:去掉DataTable重复数据(程序示例比较)
  9. (转)log4net的配置详解
  10. tar命令,转来等用
  11. 【加密】RSA加密之实现
  12. splice 操作符
  13. 导入一个新项目需要注意的几大问题(jdk1.6+eclipse4.4+tomcat6)
  14. 位置信息类API调用的代码示例合集:中国省市区查询、经纬度地址转换、POI检索等
  15. xshell连接虚拟机详解--技术流ken
  16. Arcgis瓦片--js客户端加载
  17. PHP的ob_flush()与flush()区别
  18. 类中定义的方法,self参数
  19. JS Replace 全部替换字符的用法小结
  20. px转rem

热门文章

  1. Spring Security三种认证
  2. web开发方法
  3. Java基础IO流
  4. CocoaPods报错:The dependency `` is not used in any concrete target
  5. Javascript获取各种浏览器可见窗口大小
  6. obj-c学习笔记
  7. lua例子getglobal()
  8. hdu1573(线性同余方程组)
  9. bash批量去前缀
  10. spring配置加载2次实例问题。