CodeForces - 123B Squares(简单几何+旋转坐标系)

题目链接：点击查看

题目大意：给出一个无限大的二维坐标平面，现在有一些坏点，规定：

满足以上两条件之一的点即为坏点，现在问最少经过多少个坏点的情况下，可以从起点到达终点

题目分析：一开始没想到坏点是如何分布的，看了网上题解的画图后恍然大悟了，这里借用一下图片：

来自：https://blog.csdn.net/nyist_zxp/article/details/39927781

这样就一目了然了，为了达到最优，我们只能从两条蓝线的交点处经过，所以问题转换为了求两个点之间最少需要通过多少个交点才能到达

如果直接计算因为涉及到45度直线和135度直线的问题，并不是很好计算，而正因为需要45度直线和135度直线，所以我们可以将坐标轴旋转45度后处理，旋转之后直接计算图中红线和绿线分别与多少条蓝线有交点即可，选择最大值就是答案了，还有一个小细节需要注意一下，在计算的时候如果遇到正负不同的点，还需要跨过(0,0)这个坏点，我们可以判断一下点的正负统一加上就好了，具体实现看代码

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=310;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int a,b,x1,x2,y1,y2;cin>>a>>b>>x1>>y1>>x2>>y2;a*=2,b*=2;int X1=x1+y1;int Y1=y1-x1;int X2=x2+y2;int Y2=y2-x2;x1=X1/a+(X1>0);x2=X2/a+(X2>0);y1=Y1/b+(Y1>0);y2=Y2/b+(Y2>0);printf("%d\n",max(abs(x1-x2),abs(y1-y2)));return 0; }

 

超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的CodeForces - 123B Squares(简单几何+旋转坐标系)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。