第一次打动态凸包维护dp,感觉学到了超级多的东西。

首先,set是如此的好用!!!可以通过控制一个flag来实现两种查询,维护凸包和查找斜率k

不过就是重载运算符和一些细节方面有些恶心,90行解决

后面还有一个cdq分治,找时间学下,看下能不能处理一大类恶心的问题

github还是不会用,找时间搞下吧

CODE:

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
using namespace std;
const double esp=1e-;
const int maxn=;
int dcmp(double a) {
if (fabs(a)<esp) return ;
return a<?-:;
}
struct node{
double x,y,k;bool f;
node(double _x,double _y):x(_x),y(_y),f(){}
node():f(){}
inline bool error(){return x>1e50;}
}error(1e51,);
inline bool operator == (const node x,const node y) {return dcmp(x.x-y.x)==;}
inline bool operator < (const node x,const node y){
if (x.f||y.f) return dcmp(x.k-y.k)>;
else return dcmp(x.x-y.x)<;
}
inline double operator *(const node x,const node y) {return x.x*y.y-x.y*y.x;}
inline node operator -(const node x,const node y){
node tmp;
tmp.x=x.x-y.x;tmp.y=x.y-y.y;
return tmp;
}
inline double calc_k(node x,node y) {return (x.y-y.y)/(x.x-y.x);}
set<node> gap;
typedef set<node>::iterator iter;
inline node lower(node x) {
iter it=gap.lower_bound(x);
return it==gap.end()?error:*it;
}
inline node next(node x) {
iter it=gap.upper_bound(x);
return it==gap.end()?error:*it;
}
inline node pre(node x) {
iter it=gap.lower_bound(x);
return it==gap.begin()?error:*(--it);
}
inline void ins(node a) {
if (gap.empty()) {a.k=;gap.insert(a);return;}
node d1=pre(a),d2=lower(a);
if (d1.error()&&d2.y>a.y) return ;
if ((!d1.error())&&(!d2.error())&&(dcmp((d2-d1)*(a-d1))<=)) return ;
if (d2==a) return;
node p1,p2=next(a);
for (;;){
p1=p2;p2=next(p2);
if (p1.error()||p2.error()) break;
if (dcmp((p1-a)*(p2-a))<=) break;
gap.erase(p1);
}
p2=pre(a);
for (;;){
p1=p2;p2=pre(p2);
if (p1.error()||p2.error()) break;
if (dcmp((p1-a)*(p2-a))>=) break;
gap.erase(p1);
}
d1=pre(a),d2=next(a);
if (d1.error()) a.k=;else a.k=calc_k(d1,a);gap.insert(a);
if (!d2.error()) gap.erase(d2),d2.k=calc_k(a,d2),gap.insert(d2);
}
inline double get_k(double a,double b) {
node tmp;tmp.f=;tmp.k=-a/b;
tmp=*(--gap.lower_bound(tmp));
return a*tmp.x+b*tmp.y;
}
double a[maxn],b[maxn],r[maxn],na[maxn],nb[maxn],f[maxn];
int main(){
int n,s;
scanf("%d%d",&n,&s);
for (int i=;i<=n;i++) scanf("%lf%lf%lf",a+i,b+i,r+i);
f[]=s;
nb[]=f[]/(a[]*r[]+b[]);
na[]=nb[]*r[];
ins(node(na[],nb[]));
for (int i=;i<=n;i++) {
f[i]=max(f[i-],get_k(a[i],b[i]));
nb[i]=f[i]/(a[i]*r[i]+b[i]);
na[i]=nb[i]*r[i];
ins(node(na[i],nb[i]));
}
printf("%.3f\n",f[n]);
}

  

最新文章

  1. 【三石视频教程】当FineUIPro遇到ReportViewer
  2. js-FCC算法Smallest Common Multiple。找出两个参数和它们之间的连续数字的最小公倍数。
  3. 简单介绍Android应用特色及详解四大组件
  4. GCD使用dispatch_group_notify、dispatch_group_enter、dispatch_group_leave处理多线程同步操作
  5. 思维 UVALive 3708 Graveyard
  6. ABAP字符串按长度拆分
  7. DataGridView实现分页
  8. Power Designer - 反向获取数据库物理模型时Unable to list the users 异常
  9. 开源项目Material Calendar View 学习记录 (一)
  10. jqGrid的搜索框下拉
  11. python小工具:用python操作HP的Quality Center (二)----- 用异步方式提高速度
  12. python之集合及其方法---整理集
  13. 4、Cocos2dx 3.0游戏开发找小三之Hello World 分析
  14. Pyinstaller 中 pandas出错问题的解决(详细)
  15. Retrofit源码解析(下)
  16. JAVA两种代理模式
  17. Android 手电筒源代码
  18. jQuery EasyUI 教程-Tooltip(提示框)
  19. Windows 下Java 连 MYSQL数据库
  20. 前端与HTTP

热门文章

  1. WebForm和MVC中都可以使用的路由
  2. django学习——url的name
  3. 在windows上搭建ipv6代理
  4. 云脉推出表格识别API接口可以自助接入
  5. DELPHI中MessageBox的用法
  6. js模块化开发——require.js的用法
  7. Bootstrap兼容IE8
  8. swift Alamofire请求数据与SwiftJson解析
  9. Paxos 实现日志复制同步
  10. Bootstrap入门(七)组件1:字体图标