题目传送门：I-Mr. Main and Windmills_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） (nowcoder.com)
今天和学长进行了一场icpc昆明重现赛，被打爆了。这道题都没做出来，思路其实差不多了，但是考场上没想到可以用一个eps来解决斜率为无穷的情况，shit！
题目大意
从点S，沿直线走到T点，问当点(x, y)恰好变化k次时，人所处的位置。
思路
其实要求的就是某个点，与其他所有点的连线，在直线ST上的交点，与起点的距离排序后的第k个点。
因为没经过一个这样的“关键点”，点(x, y)就会在视野中变换一次位置，第k个关键点当然就对应着：第k次变换位置的时候人所处的位置。
这里可以用vector将所有可能的点存下来后排序。
至于如何求交点嘛，请打开初中数学书。用斜率，直线表达式这样的关系直接写就行了。
注意，判断一下交点是否在ST线段上，不在线段上直接跳过。
PS：计算几何题请务必记得开long double！！！！！！！！
代码1（350ms）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long double eps = 1e-11;
const int maxn = 1e3 + 9;
int N, Q;
struct Point
{
long double x, y;//不用long double可能会wa
Point(){}
Point(long double x,long double y){this->x = x, this->y = y;}
};
Point S, T, a[maxn];
Point getCommonPoint(Point &u,Point &v)
{
long double Kst = (S.y - T.y) / (S.x - T.x + eps);//在分母加上eps
long double Kuv = (u.y - v.y) / (u.x - v.x + eps);//防止出现nan
long double Bst = S.y - Kst * S.x, Buv = u.y - Kuv * u.x;
long double x = (Buv - Bst) / (Kst - Kuv + eps);
long double y = Kst * x + Bst;
return Point(x, y);
}
long double getDist2(Point a,Point b)
{
long double dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
vector<Point> solve(int id)
{
vector<Point> res;
for(int i = 1;i <= N; ++ i)
{
if(i == id)continue;
auto tmp = getCommonPoint(a[id], a[i]);
if(tmp.x < min(S.x, T.x) || tmp.x > max(S.x, T.x))continue;
res.push_back(tmp);
}
//这里用了lambada 表达式，如果不喜欢可以自己换成函数类型的cmp
sort(res.begin(), res.end(),[](Point &a,Point &b){
return getDist2(S, a) < getDist2(S, b);
});
return res;
}
signed main()
{
cin >> N >> Q;
cin >> S.x >> S.y >> T.x >> T.y;
for(int i = 1; i <= N; ++ i)scanf("%Lf %Lf", &a[i].x, &a[i].y);
while(Q --)
{
int id, k;scanf("%lld %lld", &id, &k);
vector<Point> v = solve(id);
if(v.size() < k)printf("-1\n");
else printf("%.10Lf %.10Lf\n", v[k - 1].x, v[k - 1].y);
}
return 0;
}
这时候肯定有细心的小朋友会发现，这里的M数量级大于N，所以平均下来每个点会被询问10次，而每次询问的vector数组都一样，所以我们可以将各个点的vector先预处理出来，然后询问的时候直接输出就行了。
时间复杂度从O(N * M)优化到了O(N ^ 2)，将近10倍的差距，哈哈哈搞竞赛的就是这么执着于这些优化。
代码2（50ms）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long double eps = 1e-11;
const int maxn = 1e3 + 9;
int N, Q;
struct Point
{
long double x, y;//不用long double可能会wa
Point(){}
Point(long double x,long double y){this->x = x, this->y = y;}
};
Point S, T, a[maxn];
vector<Point> v[maxn];
Point getCommonPoint(Point &u,Point &v)
{
long double Kst = (S.y - T.y) / (S.x - T.x + eps);//在分母加上eps
long double Kuv = (u.y - v.y) / (u.x - v.x + eps);//防止出现nan
long double Bst = S.y - Kst * S.x, Buv = u.y - Kuv * u.x;
long double x = (Buv - Bst) / (Kst - Kuv + eps);
long double y = Kuv * x + Buv;
return Point(x, y);
}
long double getDist2(Point a,Point b)
{
long double dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
vector<Point> solve(int id)
{
vector<Point> res;
for(int i = 1;i <= N; ++ i)
{
if(i == id)continue;
auto tmp = getCommonPoint(a[id], a[i]);
if(tmp.x < min(S.x, T.x) || tmp.x > max(S.x, T.x))continue;
res.push_back(tmp);
}
//这里用了lambada 表达式，如果不喜欢可以自己换成函数类型的cmp
sort(res.begin(), res.end(),[](Point &a,Point &b){
return getDist2(S, a) < getDist2(S, b);
});
return res;
}
signed main()
{
cin >> N >> Q;
cin >> S.x >> S.y >> T.x >> T.y;
for(int i = 1; i <= N; ++ i)scanf("%Lf %Lf", &a[i].x, &a[i].y);
for(int i = 1;i <= N; ++ i)v[i] = solve(i);
while(Q --)
{
int id, k;scanf("%lld %lld", &id, &k);
if(v[id].size() < k)printf("-1\n");
else printf("%.10Lf %.10Lf\n", v[id][k - 1].x, v[id][k - 1].y);
}
return 0;
}
Comments NOTHING