# Kotomi【省选模拟赛】

## 复平面上的辗转相除法

Posted by yjjr's blog on March 5, 2018

n<=1e5

xi,yi<=1e9

# 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;
{
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()
{