poj 3301 Texas Trip 三分法
2024-08-26 03:31:32
思路:三分法求解凸函数的极值,三分法介绍在这:http://hi.baidu.com/czyuan_acm/item/81b21d1910ea729c99ce33db
很容易就可以推出旋转后的坐标:
x'=xcos(a)-ysin(a);
y'=ycos(a)+xsin(a).
cal(a)的意义就是在原来坐标上的点经过a弧度逆旋转后,正方形(边与坐标轴平行)最小边长要多长
cal()在旋转的时候符合凸函数,所以三分求最值
代码如下:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 100000000
#define MIN -100000000
using namespace std;
double x[],y[];
int n;
double cal(double a)
{
double maxx=MIN,maxy=MIN,minx=MAX,miny=MAX,xx,yy;
for(int i=;i<n;i++){
xx=x[i]*cos(a)-y[i]*sin(a);
yy=y[i]*cos(a)+x[i]*sin(a);
maxx=max(xx,maxx);
minx=min(xx,minx);
maxy=max(yy,maxy);
miny=min(yy,miny);
}
return max(maxx-minx,maxy-miny);
}
int main(){
int t,i;
double l,r,mid,mmid,ans;
cin>>t;
while(t--){
cin>>n;
for(i=;i<n;i++)
cin>>x[i]>>y[i];
l=0.0;
r=pi;
while(r-l>1e-){
mid=(l+r)/;
mmid=(mid+r)/;
ans=cal(mid);
if(ans<=cal(mmid)) r=mmid;
else l=mid;
}
printf("%.2lf\n",ans*ans);
}
return ;
}
最新文章
- 一些PHP性能优化汇总
- 51nod1079(中国剩余定理)
- jQuery插件 -- 动态事件绑定插件jquery.livequery.js
- wordpress导入模板数据
- Oracle用法集锦
- keepalived+LVS 实现双机热备、负载均衡、失效转移 高性能 高可用 高伸缩性 服务器集群
- MongoDB中的字段类型Id
- C#:通过Window API接口实现WiFi
- Java-->;类的成员
- jquery 页面跳转 表单提交
- random note
- 给iOS 模拟器“安装”app文件
- c#超时锁定
- HTML学习笔记 w3sCss盒子模型(阴影)(div的一些使用)案例 第十节 (原创) 参考使用表
- EntityFramework Core指定更新导航属性了解一下?
- stark组件开发之组合搜索高级显示和扩展
- table垂直居中
- Linux Kafka源码环境搭建
- 【C】C语言中的_exit()与exit()
- 动态规划:POJ No 2385 Apple Catching
热门文章
- the first blog: record my coding
- Google Breakpad part 1 : Getting Started With Windows Client
- Cursor--游标
- ecshop中无限处理分类
- 将XML文件保存到DataGridView中
- document.compatMode的CSS1compat
- [PHP]set_time_limit — 设置脚本最大执行时间
- realloc() 用法详解
- CR0,CR3寄存器
- Hello Stacked Column Chart