#dwacon5thprelimsd. [dwacon5th_prelims_d]Square Rotation

[dwacon5th_prelims_d]Square Rotation

在无限大的二维平面中有 NN 个黑点:(x1,y1),(x2,y2),,(xN,yN)(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N),剩余的点均为白点,你可以按以下规则进行无限次操作:

  • 选择一个边长为 DD 的正方形,并将其四个角上的点进行旋转,具体来说选择了一个左下角 (x,y)(x,y) 的正方形,会按以下顺序旋转:$(x,y)\rightarrow(x+D,y)\rightarrow(x+D,y+D)\rightarrow(x,y+D)\rightarrow(x,y)$

定义两个点 (x1,y1)(x_1,y_1)(x2,y2)(x_2,y_2) 的距离为 max(x1x2,y1y2)\max(\lvert x_1-x_2\rvert,\lvert y_1-y_2\rvert),你需要通过任意次操作使得平面上距离最远的两黑点的距离最小,并输出这一最小距离