标签：计算几何
题目
给定n个点的坐标(x,y)，求一个t * t的正方形网格（可以任意旋转），使得每个坐标都被网格的一个格点所覆盖。
最小化t
n<=1e5
xi,yi<=1e9
分析
如果不带旋转的网格
\[ans=gcd(X_i,Y_i)\]加入了旋转操作
我们先将一个坐标移到原点
把所有点坐标放到复平面上
设正方形网格的单位向量为e
那么每个点都可以表示成
\[(a+b_i)e\]其中a,b是整数，同样可以定义带余除法和gcd解决（然而我并不会证明gg）
之后辗转相除
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
ll lx,rx,ly,ry,n;
struct node{ll x,y;}a[maxn],num,X;
inline ll Len(node a){return a.x*a.x+a.y*a.y;}
inline ll Div(ll x,ll y){
if(x>0)return x/y+(x%y<<1>y);
x=-x;return -(x/y+(x%y<<1>y));
}
inline node operator + (node a,node b){return (node){a.x+b.x,a.y+b.y};}
inline node operator - (node a,node b){return (node){a.x-b.x,a.y-b.y};}
inline node operator * (node a,node b){return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
inline node operator / (node a,node b){return (node){Div(a.x*b.x+a.y*b.y,Len(b)),Div(a.y*b.x-a.x*b.y,Len(b))};}
inline node operator % (node a,node b){return a-(a/b)*b;}
inline node gcd(node a,node b){return Len(b)?gcd(b,a%b):a;}
int main()
{
n=read();
X=(node){read(),read()};
rep(i,2,n)num=gcd(num,a[i]=(node){read(),read()}-X);
rep(i,2,n)a[i]=a[i]/num,lx=min(lx,a[i].x),rx=max(rx,a[i].x),ly=min(ly,a[i].y),ry=max(ry,a[i].y);
printf("%lld\n",max(rx-lx,ry-ly));
return 0;
}
