ICPC昆明站I – Mr. Main and Windmills(计算几何 + long double)

发布于 2022-04-09  1556 次阅读


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