题目大意
给出 N 条垂直于 x 轴的线段, 求最大的 K, 使得存在一条经过原点, 开口向下的抛物线穿过前 K 条线段 (经过端点也算穿过), 保证 N 条线段不重叠, 且都在第一象限.
输入输出
第一行为一个整数 N;
接下来 N 行每行 3 个整数 x,y1,y2, 描述一条线段.
数据范围
N≤100000,0<x≤1e9,0<y1<y2≤1e9.
解析
设抛物线方程为 ax2+bx, 则 y1≤ax2+bx≤y2;
可以把每条线段看成两个关于 a,b 的不等式, 由于是一次的, 可以用半平面交验证答案. 于是二分 K, 验证是否可行.
几个细节:
1) 半平面在向量哪边要想清楚;
2) 由于经过端点也算穿过, 所以半平面交的边上也是可行的, 极端情况所有直线交于一点, 不知道有没有这种数据;
3) 抛物线开口向下, 对称轴在第一象限, 增加 2 个向量限制 a<0,b>0;
4) 为了方便判断半平面交是否为空, 可以增加 2 个 "边框" 向量, 但是这两个向量的起止点坐标要足够大 (反正我开 1e12WA 了);
5) 开 long double;
6) 全部排序后根据 id 加入半平面交 O(nlogn) 比每次二分都排一次序 O(nlog2n) 优秀 (废话).
代码
一直 T 竟然是因为求交点的方法不够优秀, 代码过于丑陋必须加读入优化才能过 qwq.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <iomanip>
- #include <cmath>
- #include <algorithm>
- typedef long long LL;
- typedef long double LD;
- const LD INF = 1e15;
- struct Point {
- LD x, y;
- Point(LD _x = 0, LD _y = 0):x(_x), y(_y) {};
- };
- struct Vector {
- Point st, ed;
- int id;
- LD arg;
- Vector() { memset(this, 0, sizeof(Vector)); }
- Vector(Point _st, Point _ed):st(_st), ed(_ed), id(0) {};
- bool operator <(const Vector &) const;
- friend LD cross(const Vector &, const Vector &);
- friend Point intersection(const Vector &, const Vector&);
- } line[200010];
- int N;
- bool judge(int);
- bool check(const Vector &, const Vector &, const Vector &);
- inline char gc();
- inline int read();
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("2732.in", "r", stdin);
- freopen("2732.out", "w", stdout);
- #endif
- N = read();
- line[0] = Vector(Point(0, -INF), Point(0, INF));
- line[1] = Vector(Point(-INF, 0), Point(INF, 0));
- for (int i = 1; i <= N; i++) {
- LD x = read(), y1 = read(), y2 = read();
- line[i <<1] = Vector(Point(-1, y1 / x + x), Point(1, y1 / x - x));
- line[i << 1 | 1] = Vector(Point(1, y2 / x - x), Point(-1, y2 / x + x));
- line[i << 1].id = line[i << 1 | 1].id = i;
- }
- int l = 1, r = N;
- N = (N << 1 | 1);
- line[++N] = Vector(Point(-INF, INF), Point(-INF, -INF));
- line[++N] = Vector(Point(INF, INF), Point(-INF, INF));
- for (int i = 0; i <= N; i++)
- line[i].arg = atan2(line[i].ed.y - line[i].st.y, line[i].ed.x - line[i].st.x);
- std::sort(line, line + N + 1);
- while (l < r) {
- int mid = (l + r + 1)>> 1;
- if (judge(mid)) l = mid;
- else r = mid - 1;
- }
- printf("%d\n", l);
- return 0;
- }
- bool Vector::operator <(const Vector &v) const {
- if (arg != v.arg) return arg <v.arg;
- else return cross(*this, Vector(st, v.st)) <= 0;
- }
- LD cross(const Vector &a, const Vector &b) {
- return (a.ed.x - a.st.x) * (b.ed.y - b.st.y) - (a.ed.y - a.st.y) * (b.ed.x - b.st.x);
- }
- Point intersection(const Vector &a, const Vector &b) {
- LD s1 = cross(Vector(a.st, b.ed), a);
- LD s2 = cross(a, Vector(a.st, b.st));
- LD t = s2 / (s1 + s2);
- return Point(b.st.x + t * (b.ed.x - b.st.x), b.st.y + t * (b.ed.y - b.st.y));
- }
- bool check(const Vector &a, const Vector &b, const Vector &c) {
- Point p = intersection(a, b);
- return cross(Vector(c.st, p), c)> 0;
- }
- bool judge(int lim) {
- static Vector ls[200010], res[200010];
- int tot = 0, head = 0, tail = 0;
- for (int i = 0; i <= N; i++)
- if (line[i].id <= lim) ls[tot++] = line[i];
- for (int i = 0; i <tot; i++) {
- if (i && ls[i].arg == ls[i - 1].arg) continue;
- while (tail - head> 1 && check(res[tail - 2], res[tail - 1], ls[i])) tail--;
- while (tail - head> 1 && check(res[head], res[head + 1], ls[i])) head++;
- res[tail++] = ls[i];
- }
- while (tail - head> 2 && check(res[tail - 2], res[tail - 1], res[head])) tail--;
- while (tail - head> 2 && check(res[head], res[head + 1], res[tail - 1])) head++;
- return tail - head> 2;
- }
- inline char gc() {
- static char buf[1000000], *p1, *p2;
- if (p1 == p2) p1 = (p2 = buf) + fread(buf, 1, 1000000, stdin);
- return p1 == p2 ? EOF : *p2++;
- }
- inline int read() {
- int res = 0, op = 1;
- char ch = gc();
- while (ch != '-' && (ch <'0' || ch> '9')) ch = gc();
- if (ch == '-') op = 1, ch = gc();
- while (ch>= '0' && ch <= '9')
- res = (res << 1) + (res << 3) + ch - '0', ch = gc();
- return res * op;
- }
来源: http://www.bubuko.com/infodetail-2920613.html