思路：选择每个点与其他点的连线与路线的交点（注意是否在线段上），然后sort排序。
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; typedef pair<double, double> PDD; int n, m; double sx, sy, tx, ty; double x[N], y[N]; PDD intersect(double x1, double y1, double x2, double y2) { double k1, k2; if (x1 - x2 == 0) { k1 = 1e18; } else { k1 = (y1 - y2) / (x1 - x2); } if (tx - sx == 0) { k2 = 1e18; } else { k2 = (ty - sy) / (tx - sx); } double b1 = y1 - (double)x1 * k1; double b2 = ty - (double)tx * k2; if (k1 != 1e18 && k2 != 1e18) { double x = (b2 - b1) / (k1 - k2); double y = k1 * x + b1; return {x, y}; } else { if (k1 == 1e18) { return {x1, k2 *x1 + b2}; } else { return {sx, k1 *sx + b1}; } } } int main() { cin >> n >> m; cin >> sx >> sy >> tx >> ty; vector<vector<PDD>>p(n + 1); for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; auto t = intersect(x[i], y[i], x[j], y[j]); if (t.first != 1e18) { if (t.first >= min(sx, tx) && t.first <= max(sx, tx) && t.second >= min(sy, ty) && t.second <= max(sy, ty)) p[i].push_back(t); } } if (sx < tx) sort(p[i].begin(), p[i].end()); else sort(p[i].rbegin(), p[i].rend()); } while (m--) { int idx, k; cin >> idx >> k; if (p[idx].size() < k) { cout << -1 << endl; } else { cout << fixed << setprecision(10); cout << p[idx][k - 1].first << ' ' << p[idx][k - 1].second << endl; //cout << p[idx][k - 1].first << ' ' << p[idx][k - 1].second << endl; } } return 0; }
