[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;
}
}
}