Luogu P3256：半平面交 | Yuhang's Blog

思路和现有的题解都有些差别，所以稍微写一下。

第$i$辆赛车在$t$时的路程是$x_i(t)=v_i t + x_{0i}$，每辆赛车的$x-t$图是一条直线。在同一坐标系画出所有赛车的$x-t$图，则在任意时刻$t$，领先的赛车就是高度最高的那条直线。对于所有$t$，$\max_{i} x_i(t)$构成一条折线。不难发现这条折线就是$x_i(t) \ge v_i t + x_{0i}$的半平面交的边界。 观察到这里就意识到半平面交是可以做的了。我们需要求的是在所有在某个时刻领先的赛车，其实就是对这条折线的形状作出了贡献的所有的直线。第一种情况，这自然包括在某个区间上成为了折线的直线，这对应的是某辆赛车在某个时间段保持领先。但还需要注意第二种情况，可能某辆赛车只在某个时间点（无限短暂地）保持领先，我们也认为它符合条件（正如样例提供的）。事实上第二种情况包含了第一种情况，因此这促使我们考虑折线上的所有拐点。对于所有直线，如果折线的某个拐点出现在这条直线上，那么这条直线对应的赛车就符合获奖条件。 考虑一下时间复杂度。尽管最坏情况拐点数量会几乎等于直线数量，理论时间复杂度是$O(n^2)$。但除非是非常特殊的数据，拐点数量都远小于直线的数量，所以这种做法实测比纯$O(n^2)$算法快不少。 精度问题：无脑开long double，inf取1e50，eps取1e-10可过。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=(int)(from);i<=(int)(to);++i)
#define rev(i,from,to) for(register int i=(int)(from);i>=(int)(to);--i)
#define For(i,to) for(register int i=0;i<(int)(to);++i)
typedef long long ll;
#define double long double
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9'  c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}

const double eps=1e-10;
#define inf 1e50 
#define N 11234

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
struct Point {
    double x, y;
    Point(double x=0, double y=0):x(x), y(y) { }
};
typedef Point Vector;
Vector operator+ (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator- (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator* (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator/ (Vector A, double p) { return Vector(A.x/p, A.y/p); }
bool operator< (const Point &a, const Point &b) {
    return a.x<b.x  (a.x==b.x && a.y<b.y);
}
bool operator== (const Point &a, const Point &b) {
    return a.x==b.x && a.y==b.y;
}
double Cross(const Vector &A, const Vector &B) {
    return A.x*B.y - A.y*B.x;
}
double Dot(const Vector &A, const Vector &B){
    return A.x*B.x+A.y*B.y;
}
double Length(const Vector &A) {
    return sqrt(Dot(A, A));
}

struct Line {
    Point P;
    Vector v;
    double ang;
    int index;
    Line() {}
    Line(Point P, Vector v, int index):P(P), v(v), index(index) { ang = atan2(v.y, v.x); }
    bool operator< (const Line &L) const  {
        return ang < L.ang;
    }
    double value(double x) {
        return P.y + (x - P.x) * v.y / v.x;
    }
};
bool OnLeft(Line L, Point p) {
    return Cross(L.v, p-L.P) > 0;
}
Point GetIntersection(Line a, Line b) {
    Vector u = a.P-b.P;
    double t = Cross(b.v, u) / Cross(a.v, b.v);
    return a.P+(a.v*t);
}

void HalfplaneIntersection(vector<Line> &L, vector<Point> &ret) {
    sort(L.begin(), L.end());
    Point *p = new Point[N];
    Line *q = new Line[N];
    int first, last;
    q[first=last=0] = L[0];
    for(int i = 1; i < L.size(); i++) {
        while(first < last && !OnLeft(L[i], p[last-1])) --last;
        while(first < last && !OnLeft(L[i], p[first])) ++first;
        q[++last] = L[i];
        if (!dcmp(Cross(q[last].v, q[last-1].v))) {
            --last;
            if(OnLeft(q[last], L[i].P)) q[last] = L[i];
        }
        if (first < last) p[last-1] = GetIntersection(q[last-1], q[last]);
    }
    while(first < last && !OnLeft(q[first], p[last-1])) --last;
    if (last - first <= 1) return;
    p[last] = GetIntersection(q[last], q[first]);
    for(int i = first; i <= last; i++) {
        if (p[i].y >= inf) continue;
        ret.push_back(p[i]);
    }
}

double b[N], k[N];
vector<Point> ret;
vector<int> ans;
vector<Line> L;

int main() {
    int n = read();
    rep(i, 1, n) cin >> b[i];
    rep(i, 1, n) {
        cin >> k[i];
        Line l = Line(Point(0, b[i]), Vector(1, k[i]), i);
        L.push_back(l);
    }
    L.push_back(Line(Point(0, 0), Vector(0, -1), 0));
    L.push_back(Line(Point(0, 0), Vector(1, 0), 0));
    L.push_back(Line(Point(inf, 0), Vector(0, 1), 0));
    L.push_back(Line(Point(0, inf), Vector(-1, 0), 0));

    HalfplaneIntersection(L, ret);

    for(auto l : L) {
        if (l.index == 0) continue;
        for(auto p : ret) {
            if (!dcmp(l.value(p.x) - p.y)) {
                ans.push_back(l.index);
                break;
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    For(i, ans.size()) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}