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

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

Description

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

Input

输入文件第一行是一个正整数 N N $N$ ，表示一共有 N" role="presentation" style="position: relative;">NN$N$ 关。接下来有 N N $N$ 行，第 i+1" role="presentation" style="position: relative;">i+1i+1$i+1$ 行是用空格隔开的三个正整数 xi x i $x_i$ ， yi,1 y i , 1 $y_{i,1}$ ， yi,2 y i , 2 $y_{i,2}$ （ yi,1<yi,2 y i , 1 < y i , 2 $y_{i,1}<y_{i,2}$ ），表示第 i i $i$ 关出现的靶子的横坐标是 xi" role="presentation" style="position: relative;">xixi$x_i$ ，纵坐标的范围是从 yi,1 y i , 1 $y_{i,1}$ 到 yi,2 y i , 2 $y_{i,2}$ 。
输入保证 30% 的数据满足 N≤100 N ≤ 100 $Nle100$ ， 50% 的数据满足 N≤5000 N ≤ 5000 $Nle5000$ ， 100% 的数据满足 N≤100000 N ≤ 100000 $Nle100000$ 且给出的所有坐标不超过 109 10 9 $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=ax2+bx y = a x 2 + b x $y=ax^2+bx$ 对于一个靶子 x,y1,y2 x , y 1 , y 2 $x,y_1,y_2$ 合法的条件：

y1≤ax2+bx≤y2 y 1 ≤ a x 2 + b x ≤ y 2 $$y_1le ax^2+bxle y_2$$
由于 x>0 x > 0 $x>0$ ，因此考虑将等式除以 x x $x$ ：
y1x&#x2264;ax+b&#x2264;y2x" role="presentation" style="text-align: center; position: relative;">y1x≤ax+b≤y2xy1x≤ax+b≤y2x $$frac{y_1}xle ax+blefrac{y_2}x$$
而此时点 (a,b) ( a , b ) $(a,b)$ 既在半平面 ax+b≥y1x a x + b ≥ y 1 x $ax+bgefrac{y_1}x$ 内，也在半平面 ax+b≤y2x a x + b ≤ y 2 x $ax+blefrac{y_2}x$ 内。
考虑二分答案，如果要判定能否通过前 mid m i d $mid$ 关，那么就把前 mid m i d $mid$ 个靶子分别对应的 2×mid 2 × m i d $2times mid$ 个半平面加入，再加入两个限制条件 a<0 a < 0 $a<0$ 和 b>0 b > 0 $b>0$ ，判断半平面交是否有可行域即可。
为了使判定的复杂度为线性，可以在二分前先将所有 2×n+2 2 × n + 2 $2times 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;
}