题目传送门: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