BZOJ2402 陶陶的难题II
<div class="post_brief"><p> orz mhy。看mhy的刷题记录成为了我成天的刷题方向了。</p> 其实最初也没有想清楚。然后看了一眼mhy写的题解写了凸壳,秒懂。 二分一个答案,设它是ans。如果ans≥realAns的话,那么就会存在yi-ans*xi+qj-ans*pj≥0。然后i和j就分开了。于是变成了求一条路径上yi-ans*xi的最大值。把xi看作k,把yi看作b,就变成半平面交了。于是开归并式线段树把凸壳给记录下来就好了。然后复杂度大约是单次询问O(lg3(n))的?链剖后每棵树单独建树,然后复杂度我就不会算了TT。 于是就硬着头皮写了,然后发现跑得还挺快。 #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 30009; const int maxl = 15; const int max_buf = maxn * maxl * 2; const double eps = 1e-6; const double finf = 1e10; int ibuf_arr[max_buf], *ibuf(ibuf_arr); double fbuf_arr[max_buf], *fbuf(fbuf_arr); struct edge { int t; edge *next; }; struct line { double k, b; inline double xCross(const line& a) { return (a....