[BZOJ2732][HNOI2012]射箭（二分答案+半平面交）

Description

沫沫最近在玩一个二维的射箭游戏，如下图 $1$ 所示，这个游戏中的 $x$ 轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。沫沫控制一个位于 $(0,0)$ 的弓箭手，可以朝 $0$ 至 $90$ 中的任意角度（不包括 $0$ 度和 $90$ 度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些只有端点被射中的靶子。这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。在闯关模式中，第一关只有一个靶子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外一个靶子，若能够一箭双雕射中这两个靶子便可进入第三关，这时会出现第三个靶子。依此类推，每过一关都会新出现一个靶子，在第 $K$ 关必须一箭射中前 $K$ 关出现的所有 $K$ 个靶子才能进入第 $K+1$ 关，否则游戏结束。沫沫花了很多时间在这个游戏上，却最多只能玩到第七关“七星连珠”，这让她非常困惑。 于是她设法获得了每一关出现的靶子的位置，想让你告诉她，最多能通过多少关？

Input

输入文件第一行是一个正整数 $N$ ，表示一共有 $N$ 关。接下来有 $N$ 行，第 $i+1$ 行是用空格隔开的三个正整数 $x_i$ ， $y_{i,1}$ ， $y_{i,2}$ （ $y_{i,1}<y_{i,2}$ ），表示第 $i$ 关出现的靶子的横坐标是 $x_i$ ，纵坐标的范围是从$y_{i,1}$ 到 $y_{i,2}$ 。
输入保证 30% 的数据满足 $N\le100$ ， 50% 的数据满足 $N\le5000$ ， 100% 的数据满足 $N\le100000$ 且给出的所有坐标不超过 $10^9$ 。

Output

仅包含一个整数，表示最多的通关数。

Sample Input

5
2 8 12
5 4 5
3 8 10
6 2 3
1 3 7

Sample Output

3

HINT

Solution

考虑一个抛物线 $y=ax^2+bx$ 对于一个靶子 $x,y_1,y_2$ 合法的条件：

$$y_1\le ax^2+bx\le y_2$$
由于 $x>0$ ，因此考虑将等式除以 $x$ ：
$$\frac{y_1}x\le ax+b\le\frac{y_2}x$$
而此时点 $(a,b)$ 既在半平面 $ax+b\ge\frac{y_1}x$ 内，也在半平面 $ax+b\le\frac{y_2}x$ 内。
考虑二分答案，如果要判定能否通过前 $mid$ 关，那么就把前 $mid$ 个靶子分别对应的 $2\times mid$ 个半平面加入，再加入两个限制条件 $a<0$ 和 $b>0$ ，判断半平面交是否有可行域即可。
为了使判定的复杂度为线性，可以在二分前先将所有 $2\times n+2$ 个半平面进行极角排序。
此外，注意 玄学的，恶心的，丧病的卡精度。

Source

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
inline int read() {int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}
const int N = 214748; int n, tn;
struct cyx {double x, y;friend inline cyx operator + (cyx a, cyx b) {return (cyx) {a.x + b.x, a.y + b.y};}friend inline cyx operator - (cyx a, cyx b) {return (cyx) {b.x - a.x, b.y - a.y};}friend inline cyx operator * (cyx a, double b) {return (cyx) {a.x * b, a.y * b};}friend inline cyx operator / (cyx a, double b) {return (cyx) {a.x / b, a.y / b};}friend inline double operator * (cyx a, cyx b) {return a.x * b.y - a.y * b.x;}
};
struct pyz {cyx a, b; int id; double it; cyx o() {return a - b;}} a[N], b[N], q[N];
bool check(cyx a, pyz b) {return b.o() * (b.a - a) > 0;}
bool comp(pyz a, pyz b) {if (a.it != b.it) return a.it < b.it; return (a.a - b.a) * (a.a - b.b) > 0;
}
cyx weak(pyz x, pyz y) {double s1 = (x.a - y.b) * (x.a - y.a), s2 = (x.b - y.a) * (x.b - y.b);return x.a + x.o() * s1 / (s1 + s2);
}
bool lpf(cyx a, pyz b) {return (a - b.b) * (a - b.a) > 0;}
bool cyxisdalao(int mid) {int i, n = 0, H = 1, T = 2; For (i, 1, tn) if (b[i].id <= mid &&(!n || b[i].it > a[n].it)) a[++n] = b[i]; q[1] = a[1]; q[2] = a[2];For (i, 3, n) {while (H < T && lpf(weak(q[T - 1], q[T]), a[i])) T--;while (H < T && lpf(weak(q[H], q[H + 1]), a[i])) H++;q[++T] = a[i];}while (H < T && lpf(weak(q[T - 1], q[T]), q[H])) T--;return T - H > 1;
}
int main() {int i, x, y1, y2; n = read();b[++tn] = (pyz) {(cyx) {0, 0}, (cyx) {0, 1}, 0};b[++tn] = (pyz) {(cyx) {0, 0}, (cyx) {1, 0}, 0}; For (i, 1, n) {x = read(); y1 = read(); y2 = read();double x1 = 1.0 * y1 / x, x2 = 1.0 * y2 / x;b[++tn] = (pyz) {(cyx) {0, x1}, (cyx) {1, x1 - x}, i};b[++tn] = (pyz) {(cyx) {1, x2 - x}, (cyx) {0, x2}, i};}For (i, 1, tn) b[i].it = atan2(b[i].b.y - b[i].a.y, b[i].b.x - b[i].a.x);sort(b + 1, b + tn + 1, comp); int l = 1, r = n; while (l <= r) {int mid = l + r >> 1;if (cyxisdalao(mid)) l = mid + 1; else r = mid - 1;}cout << r << endl; return 0;
}