洛谷P5088 【矩形】

发表于 | 更新于 | 分类于 | 阅读次数：

OI退役想去搞物理竞赛的我还是太弱了

初中物理的光学竞赛问题，基于反射角=入射角，我们可以拿张草稿纸手膜小样例最终推出答案。

  • 对于$N=M$的情况：

不妨设N=M=1，先手膜一组$2*3$的数据（绿线是经折射的线，蓝点为反射点）：

这里用了反射角=入射角的原理，关于射线的折射点反复对称就得到这张图。

可以注意到第三行我标了两个蓝点，这是因为我标错了这两个点关于法线对称，因此可以等价看待。

然后我们就可以注意到一个有趣的事实，我们设$AB$是从入射点不考虑折射，直接引出的且起始点为网格点的最短线段，可以发现3个蓝点均在$AB$上！

于是我们可以大胆得出结论：对于任意AB为对角线形成的最小矩形，与其他网格点所形成的交点即为反射的次数。

若矩形大小为$a,b$，每行会有一个交点，每列也会有一个交点，减去B所在的点的贡献，答案即为$a+b-2$，10分到手

  • 对于$A=B$

等价于是$tan ζ =1$的情况，不妨设$A=B=1$，我们先手膜一个$3*5$的表格（很丑）：

经观察我们发现：经上下边界反射的点数=列数；经左右边界反射的点数=行数

咋证明呢？我好像不太会啊。

（一本正经的胡说八道）其实我们可以用映射的思想，因为我们求的均是长宽比值，所以具体大小是不影响答案的，我们可以感性的将这个大矩形压缩成一个单位1的正方形，如图：

你看这个小正方形和那个大矩形是不是很像！？

此时原本$tanζ=1$的线应是被我们压缩成了$tan ζ=A/B=3/5$，相当于我们就可以直接引用第一种情况的结论得出答案辣！第二个10分的结论就是$n+m-2$

  • 正解

想到了映射还有什么问题没解决了吗？？

我们只要把任意数据都替换成$N=M$的情况，直接套结论就可以啦！

对于水平方向的$N,a$同时除以N，竖直方向的$M,b$同时除以M，可以证明与原来的数据是等价的。

此时修改过后的$N=M=1$，那么对于a1与b1先使他们互质，再直接套第一种情况的结论就行啦！

最后还有记得特判a=0,b=0的情况。。死活卡在95就是这个原因。

最后，上丑陋的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#define ll long long
using namespace std;
ll n,m,a,b;

ll gcd(ll a,ll b)
{
	return (!b)?a:gcd(b,a%b); 
}

int main()
{
	cin>>n>>m;
	cin>>a>>b;
	a*=m; b*=n; //与a/n,b/m等价，而且这样可以保证a,b为整数
	ll d=gcd(a,b); 
	if (a==0||b==0) {
		cout<<0<<endl; return 0;
	}
	a/=d; b/=d;
	cout<<b+a-2<<endl;
}

大冬天待在空调房，可能脑子不是很好使，如有错误指出_(:з」∠)