记录编号	95644	评测结果	AAAAAAAAAA
题目名称	[POI 2002]超级马	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.056 s
提交时间	2014-04-08 10:37:22	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEN=110;
int N;
int x[SIZEN]={0},y[SIZEN]={0};
int gcd(int a,int b){
	return !b?a:gcd(b,a%b);
}
bool check(int a[SIZEN],int b[SIZEN]){//a的和应当为0,b的和应当为±1
	/*
	先测试能否整数地摞出来±1
	然后测试有没有非负解,即测试能否非负地摞出来"一正一负"的b和,同时a和为零
	构造方法是:先摞出来每个操作都几乎无穷多次,且a和为零的"基础",
	用非负摞出来的b和去补偿刚才的b和,最后用不限正负的和微调到±1
	而且这个"一正一负"是必要的,否则无法到达b和的无穷远点
	*/
	bool pos,neg;//正负是否都存在
	pos=neg=false;
	for(int i=1;i<=N;i++){
		if(a[i]>0) pos=true;
		if(a[i]<0) neg=true;
	}
	if(!pos||!neg) return false;//如果a都非正或都非负绝对不行
	pos=neg=false;
	for(int i=1;i<=N;i++){
		if(!a[i]){
			if(b[i]>0) pos=true;
			if(b[i]<0) neg=true;
		}
	}
	int g=0;
	for(int i=1;i<=N;i++) if(!a[i]) g=gcd(g,abs(b[i]));
	for(int i=1;i<=N;i++){
		if(!a[i]) continue;
		for(int j=i+1;j<=N;j++){//需要考察i,j当a=0的最小b和
			if(!a[j]) continue;
			int d=gcd(abs(a[i]),abs(a[j]));
			int t=b[i]*(a[j]/d)-b[j]*(a[i]/d);
			g=gcd(g,abs(t));
			if(a[i]*a[j]<0){//a[i],a[j]一正一负
				t=b[i]*abs(a[j]/d)+b[j]*abs(a[i]/d);
				if(t>0) pos=true;
				if(t<0) neg=true;
			}
		}
	}
	if(g!=1) return false;
	if(!neg||!pos) return false;
	return true;
}
void work(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d%d",&x[i],&y[i]);
	if(check(x,y)&&check(y,x)) printf("TAK\n");
	else printf("NIE\n");
}
int main(){
	freopen("superknight.in","r",stdin);
	freopen("superknight.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}