记录编号	230354	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2005] 骑士	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2016-02-21 14:54:52	内存使用	0.29 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=110;
int N;
int vec[SIZEN][2];
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&vec[i][0],&vec[i][1]);
		if(vec[i][0]<0) vec[i][0]*=(-1),vec[i][1]*=(-1);
	}
}
int gcd(int a,int b,int &x,int &y)
{
	if(b==0){ x=1,y=0;return a;}
	int re=gcd(b,a%b,y,x);
	y-=a/b*x;
	return re;
}
void work()
{
	int A[2],B[2]={0},C[2];
	A[0]=vec[1][0],A[1]=vec[1][1];
	for(int i=2;i<=N;i++)
	{
		int x,y;
		if(vec[i][0]==0) C[0]=0,C[1]=vec[i][1];
		else
		{
		int g=gcd(A[0],vec[i][0],x,y);
		C[0]=0,C[1]=(A[0]*vec[i][1]-A[1]*vec[i][0])/g;
		A[0]=g;A[1]=A[1]*x+vec[i][1]*y;
		}
		if(C[1]==0) continue;
		else if(B[1]==0) B[1]=C[1];
		else B[1]=gcd(B[1],C[1],x,y);
	}
	printf("%d %d\n",A[0],A[1]);
	printf("%d %d\n",B[0],B[1]);
}
int main()
{
	freopen("knight_poi2005.in","r",stdin);
	freopen("knight_poi2005.out","w",stdout);
	read();
	work();
	return 0;
}