题意:给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 ;
}

最新文章

  1. 帮我做个APP,给你20万,做不做?
  2. c# 读取mck码
  3. C# 委托如何理解 打个比喻
  4. Android Animation学习(三) ApiDemos解析:XML动画文件的使用
  5. Apache Error: Invalid command ‘Allow’, perhaps misspelled or defined by a module not included in the server configuration
  6. JSON解析例子
  7. 【BZOJ3529】【莫比乌斯反演 + 树状数组】[Sdoi2014]数表
  8. 不使用TNS直连数据库的三种方式
  9. C++ Primer 学习笔记_44_STL实践与分析(18)--再谈迭代器【下】
  10. Swift游戏开发实战教程(霸内部信息大学)
  11. js立即执行函数: (function ( ){...})( ) 与 (function ( ){...}( ))
  12. Centos7下安装部署MXNET
  13. VR虚拟现实技术在教育领域的前景展望
  14. 关于JAVA正则匹配空白字符的问题
  15. C#利用微软企业库Enterprise Library配置mysql数据库
  16. Error:&quot;MetaStoreClient lost connection. Attempting to reconnect (1 of 24) after 5s. getCurrentNotificationEventId&quot; occurs as HiveServer2 fails to start as it cannot connect to Metastore in HDP 3.0
  17. nginx正则匹配
  18. 《CSS世界》读书笔记(八)
  19. MariaDB 插入&amp;更新&amp;删除数据(8)
  20. System.ConfigurationManager类用于对配置文件的读取

热门文章

  1. &lt;select multiple=&quot;multiple&quot;&gt; 数据回显
  2. UOJ131 [NOI2015] 品酒大会
  3. 磁盘I/O工作原理
  4. map简单用法
  5. sublime text 3插件下载教程
  6. 在Developerkit开发板上运行blink例程
  7. 用DELPHI中实现RAR文件解压到指定一目录
  8. router登录逻辑实现页面跳转
  9. CocoaPods中pod search报错的解决办法
  10. window使用