Kotomi【省选模拟赛】

复平面上的辗转相除法

Posted by yjjr's blog on March 5, 2018

标签:计算几何

题目

给定n个点的坐标(x,y),求一个t * t的正方形网格(可以任意旋转),使得每个坐标都被网格的一个格点所覆盖。

最小化t

n<=1e5

xi,yi<=1e9

分析

如果不带旋转的网格

加入了旋转操作

我们先将一个坐标移到原点

把所有点坐标放到复平面上

设正方形网格的单位向量为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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr