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