洋葱第4场C和D题解……

时间:2021-09-12 10:31:15

只是记录一下:

我们机房讨论的结果……(当然有一个au爷一开始就秒掉了……
首先先n^2或随机枚举出一对点
根据抽屉原理可得枚举(n/2)^2+1次后至少有一对点全是对的
然后对于两个对的点,首先考虑缩放比例
不论是旋转还是平移两个点之间的距离都不会改变
而缩放对两点间的距离改变的倍数就等于缩放的倍数
(因为相似三角形
所以缩放就求出来了
然后可以发现缩放和旋转其实可以反过来
那么把缩放放到前面,现在考虑中间只有旋转和平移
对于旋转
因为平移不会改变两个点之间连线的斜率,所以直接根据斜率的变化可以求出旋转角
然后结合旋转角和缩放比就可以直接把平移偏移量求出来了
此题完结
(核心思路就是两个点之间相对的某个值不会随其中的两个操作而改变,只会随剩下的一个操作改变,根据这个就可以根据唯一一个会影响两个点之间相对的某个值的操作直接得出某操作的值了……