题解 | #[JLOI2013]赛车#

半平面交模板题 不了解的可以去学习一下~

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
const int maxn = 10010;
const long double eps = 1e-18;
#define x first
#define y second
typedef long double LD;
typedef pair<LD, LD> PDD;
typedef pair<int,int> PII;
typedef struct node
{
    PDD st, ed;
    vector<int> ids;
}Line;
Line lines[maxn];
int ki[maxn], vi[maxn];
int q[maxn], ans[maxn];
int n, cnt;
PDD operator - (PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}
int sign(LD x)
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}
int dcmp(LD x, LD y)
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}
LD cross(PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}
LD area(PDD a, PDD b, PDD c)
{
    return cross(b - a, c - a);
}
LD get_angle(Line a)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}
bool cmp(const Line &a, const Line &b)
{
    LD thetaA = get_angle(a), thetaB = get_angle(b);
    if(!dcmp(thetaA, thetaB)) return area(a.st, a.ed, b.ed) < 0;
    return thetaA < thetaB;
}
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    LD t = cross(w, u) / cross(v, w);
    return {p.x + t * v.x, p.y + t * v.y};
}
PDD get_line_intersection(Line a, Line b)
{
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}
bool on_right(Line a, Line b, Line c)
{
    auto o = get_line_intersection(b, c);
    return area(a.st, a.ed, o) < 0;
}
void half_plane_intersection()
{
    sort(lines, lines + cnt, cmp);
    int hh = 0, tt = -1;
    for(int i = 0; i < cnt; i ++){
        if(i && !dcmp(get_angle(lines[i]), get_angle(lines[i - 1]))) continue;
        while(hh + 1 <= tt && on_right(lines[i], lines[q[tt - 1]], lines[q[tt]])) tt --;
        while(hh + 1 <= tt && on_right(lines[i], lines[q[hh]], lines[q[hh + 1]])) hh ++;
        q[++ tt] = i;
    }
    while(hh + 1 <= tt && on_right(lines[q[hh]], lines[q[tt - 1]], lines[q[tt]])) tt --;
    while(hh + 1 <= tt && on_right(lines[q[tt]], lines[q[hh]], lines[q[hh + 1]])) hh ++;
    int k = 0;
    for(int i = hh; i <= tt; i ++){
        for(auto id : lines[q[i]].ids){
            ans[k ++] = id;
        }
    }
    sort(ans, ans + k);
    cout << k << endl;
    for(int i = 0; i < k; i ++) cout << ans[i] + 1 << ' ';
    cout << endl;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    map<PII, vector<int>> mp;
    for(int i = 0; i < n; i ++) cin >> ki[i];
    for(int i = 0; i < n; i ++) cin >> vi[i];
    for(int i = 0; i < n; i ++){
        mp[{ki[i], vi[i]}].push_back(i);
    }
    lines[cnt ++] = {{0, 10000}, {0, 0}};
    lines[cnt ++] = {{0, 0}, {10000, 0}};
    for(auto [k, v] : mp){
        lines[cnt ++] = {{0, k.x}, {1, k.x + k.y}, v};
    }
    half_plane_intersection();
    return 0;
}