? 解题记录 ? ? 洛谷 ? ? 半平面交 ?    2018-11-25 16:57:21    697    0    0

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

`3`

## 这题的坑在于不仅仅是靶子对抛物线有限制，还有生活实际的限制。首先抛物线必须开口朝下(a<0)，其次落点必须在y轴右侧(b>0)。

```// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 4e5 + 20;
const long double inf = 1e12;
const long double x0 = -20;
const long double x1 = 19;
int vis[maxn], n, cnt, x, h, l;

namespace G2D {
typedef long double T;
const T eps = 1e-18;
int sgn(T x) {return (x > -eps) - (x < eps);}
struct Point {
T x, y; Point(){}
Point(T rx, T ry) {x = rx, y = ry;}
void prt() {
//cerr << x << " " << y << endl;
printf("%lf %lf\n", x, y);
}
};
Point operator + (const Point &A, const Point &B) {
return Point(A.x + B.x, A.y + B.y);
}
Point operator - (const Point &A, const Point &B) {
return Point(A.x - B.x, A.y - B.y);
}
T operator * (const Point &A, const Point &B) {
return (A.x * B.y - B.x * A.y);
}
Point operator * (const Point &A, const T &B) {
return Point(A.x * B, A.y * B);
}
struct Line {
T k; int id;
Point s, t;Line() {}
Line(Point rx, Point ry)
{s = rx, t = ry, id = 0;}
void calc() {
k = atan2((t - s).x, (t - s).y);
}
bool operator < (const Line &A) const {
return sgn(A.k - k) > 0;
}
};
Point cross(const Line &A, const Line &B) {
T s1 = ((B.t - A.s) * (B.s - A.s)), s2 = ((B.s - A.t) * (B.t - A.t));
return (A.t - A.s) * (s1 / (s1 + s2)) + A.s;
}
int AOnLeft(const Point &A, const Line &B) {
return sgn((B.t - B.s) * (A - B.s));
}
int q[maxn], f, b;
bool HPI(Line *l, int cnt, int x) {
int tp = 0, tot = 0, lst = 0; f = 1, b = 0;
while(tp < cnt) {
++tp;
while(tp <= cnt && l[tp].id > x)
++tp;
if(tp == cnt + 1) break;
//if(f < b) cross(l[q[b - 1]], l[q[b]]).prt();
while(f < b && AOnLeft(cross(l[q[b - 1]], l[q[b]]), l[tp]) < 0)
--b;
//if(f < b) cross(l[q[f]], l[q[f + 1]]).prt();
while(f < b && AOnLeft(cross(l[q[f]], l[q[f + 1]]), l[tp]) < 0)
++f;
q[++b] = tp;
//if (!sgn((l[q[b]].t - l[q[b]].s) * (l[q[b - 1]].t - l[q[b - 1]].s))) {
//    --b;
//}
}
while(f < b && AOnLeft(cross(l[q[b - 1]], l[q[b]]), l[q[f]]) < 0)
--b;
while(f < b && AOnLeft(cross(l[q[f]], l[q[f + 1]]), l[q[b]]) < 0)
++f;
/*printf("#######\n");
for(register int i = f; i < b; ++i)
cross(l[i], l[i + 1]).prt();
cross(l[b], l[f]).prt();*/
if(b <= f + 1) return 0;
return 1;
}
}
using namespace G2D;
Line ls[maxn], nls[maxn];
int tp;

int solve(int l, int r) {
while(l < r - 1) {
int mid = l + r >> 1;
if(G2D::HPI(nls, tp, mid)) l = mid;
else r = mid;
}
return l;
}

int main() {
//freopen("input8.in", "r", stdin);
//freopen("log.txt", "w", stdout);
scanf("%d", &n);
/*for(register int i = 1; i <= n; ++i) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
ls[++cnt] = Line(Point(a, b), Point(c, d));
ls[cnt].calc(), ls[cnt - 1].calc();
}
sort(ls + 1, ls + cnt + 1);
printf("%d", HPI(ls));*/
for(register int i = 1; i <= n; ++i) {
scanf("%d%d%d", &x, &l, &h);
ls[++cnt] = Line(Point(x1, h * 1.0 / x - x1 * x),
Point(x0, h * 1.0 / x - x0 * x));
ls[++cnt] = Line(Point(x0, l * 1.0 / x - x0 * x),
Point(x1, l * 1.0 / x - x1 * x));
ls[cnt].id = ls[cnt - 1].id = i;
ls[cnt].calc(), ls[cnt - 1].calc();
}
ls[++cnt] = Line(Point(-eps, inf), Point(-inf, inf));
ls[cnt].calc();
ls[++cnt] = Line(Point(-inf, inf), Point(-inf, eps));
ls[cnt].calc();
ls[++cnt] = Line(Point(-inf, eps), Point(-eps, eps));
ls[cnt].calc();
ls[++cnt] = Line(Point(-eps, eps), Point(-eps, inf));
ls[cnt].calc();
sort(ls + 1, ls + cnt + 1), nls[tp].k = 66662333;
for(register int i = 1; i <= cnt; ++i) {
if(sgn(nls[tp].k - ls[i].k)) nls[++tp] = ls[i];
else if(AOnLeft(ls[i].s, nls[tp]) > 0)
nls[tp] = ls[i];
}
printf("%d", solve(1, n + 1));
//cout << check(88888);
return 0;
}
```

697 人读过

0 条评论