AtCoder Beginner Contest 130 F Minimum Bounding Box 三分法求极值(WA)
2024-09-02 18:29:17
题意:给n个点的起始坐标以及他们的行走方向,每一单位时间每个点往它的方向移动一单位。问最小能包围所有点的矩形。
解法:看到题目求极值,想了想好像可以用三分法求极值,虽然我也不能证明面积是个单峰函数。
尝试交了一发结果73组数据WA了1组数据,看起来似乎三分法是对的,但是至今还没找到哪个细节错了qwq,先记录下来。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
const int INF=0x3f3f3f3f;
const double eps=1e-;
int n,m,x[N],y[N];
char d[N][]; double xmax,xmin,ymax,ymin;
void chg(double x,double y) {
xmax=max(xmax,x); xmin=min(xmin,x);
ymax=max(ymax,y); ymin=min(ymin,y);
} double calc(double t) {
xmax=-INF,xmin=INF,ymax=-INF,ymin=INF;
for (int i=;i<=n;i++) {
if (d[i][]=='R') chg(x[i]+t,y[i]);
if (d[i][]=='L') chg(x[i]-t,y[i]);
if (d[i][]=='U') chg(x[i],y[i]+t);
if (d[i][]=='D') chg(x[i],y[i]-t);
}
return (double)(xmax-xmin)*(ymax-ymin);
} int main()
{
cin>>n;
for (int i=;i<=n;i++) scanf("%d%d%s",&x[i],&y[i],d[i]);
double l=,r=1e8, lm, rm;
while(r-l>eps) {
lm = l+(r-l)/;
rm = lm+(r-lm)/;
if(calc(lm) < calc(rm)) r = rm;
else if(calc(lm) == calc(rm)) r=rm, l=lm;
else l = lm;
}
printf("%.10lf\n",calc(l));
return ;
}
最新文章
- 帮我做个APP,给你20万,做不做?
- c# 读取mck码
- C# 委托如何理解 打个比喻
- Android Animation学习(三) ApiDemos解析:XML动画文件的使用
- Apache Error: Invalid command ‘Allow’, perhaps misspelled or defined by a module not included in the server configuration
- JSON解析例子
- 【BZOJ3529】【莫比乌斯反演 + 树状数组】[Sdoi2014]数表
- 不使用TNS直连数据库的三种方式
- C++ Primer 学习笔记_44_STL实践与分析(18)--再谈迭代器【下】
- Swift游戏开发实战教程(霸内部信息大学)
- js立即执行函数: (function ( ){...})( ) 与 (function ( ){...}( ))
- Centos7下安装部署MXNET
- VR虚拟现实技术在教育领域的前景展望
- 关于JAVA正则匹配空白字符的问题
- C#利用微软企业库Enterprise Library配置mysql数据库
- Error:";MetaStoreClient lost connection. Attempting to reconnect (1 of 24) after 5s. getCurrentNotificationEventId"; occurs as HiveServer2 fails to start as it cannot connect to Metastore in HDP 3.0
- nginx正则匹配
- 《CSS世界》读书笔记(八)
- MariaDB 插入&;更新&;删除数据(8)
- System.ConfigurationManager类用于对配置文件的读取