ICPC昆明站I - Mr. Main and Windmills（计算几何 + long double）

题目传送门：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;
}