[ICPC2020昆明I] Mr. Main and Windmills - 计算几何

Description

Mr.Main坐火车从s到t，经过了许多风车。火车在一条直线上行驶。随着火车的行驶，风车在Mr.Main的视野里会发生位置相对变化。现在给出风车们的坐标，请你找到当第h个风车与其他风车的相对位置变化k次时火车的位置。\(n\le 1000\)

Solution

将任意两点确定的直线与给定线段的交点算出来排序，然后顺序扫描一遍将所有交换事件塞进 vector，询问时直接查询即可

#include <bits/stdc++.h>
using namespace std;

vector<tuple<double, int, int>> events; // 交换事件列表

const int N = 1005;

struct vec2
{
    double x, y;
    vec2 operator+(const vec2 &rhs) const
    {
        return {x + rhs.x, y + rhs.y};
    }

    vec2 operator-(const vec2 &rhs) const
    {
        return {x - rhs.x, y - rhs.y};
    }

    double operator*(const vec2 &rhs) const
    {
        return x * rhs.x + y * rhs.y;
    }

    double operator%(const vec2 &rhs) const
    {
        return x * rhs.y - y * rhs.x;
    }

    bool operator<(const vec2 &rhs) const
    {
        return (*this) % rhs < 0;
    }

    vec2 operator*(double r) const
    {
        return {x * r, y * r};
    }
};

int n, m;

vec2 s, t, d;

vec2 p[N];

vector<double> ans[N];

double get_lambda(vec2 a, vec2 b)
{
    double p = (s - b) % (s - a);
    double q = d % (a - b) + 1e-18;
    return p / q;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m >> s.x >> s.y >> t.x >> t.y;
    d = t - s;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;

    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            double r = get_lambda(p[i], p[j]);
            if (r >= 0 && r <= 1)
            {
                events.push_back(make_tuple(r, i, j));
            }
        }
    }

    sort(events.begin(), events.end());

    for (auto [r, i, j] : events)
    {
        ans[i].push_back(r);
        ans[j].push_back(r);
    }

    for (int i = 1; i <= m; i++)
    {
        int h, k;
        cin >> h >> k;
        if (k > ans[h].size())
            cout << -1 << endl;
        else
        {
            double r = ans[h][k - 1];
            vec2 pos = s + d * r;
            cout << fixed << setprecision(12) << pos.x << " " << pos.y << endl;
        }
    }
}

[ICPC2020昆明I] Mr. Main and Windmills - 计算几何