ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年4月9日 1239点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ icpc 牛客网 算法竞赛 计算几何
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码1(350ms)
  • 代码2(50ms)

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号