记录编号	374548	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Mar10]星牛争霸	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.468 s
提交时间	2017-02-23 13:34:42	内存使用	46.53 MiB

#include<cstdio>
#include<cmath>
using namespace std;
typedef double db;
const int N=2010;
const db eps=1e-10;
int n,m=3,M,v[N][N];
db a[N][N];
char s[10];
//假定第一种单位的战斗力是1 
void gete(bool tp,int *v){
	for (int i=0;i<m;i++)
		v[i]=tp?v[i]-v[i+m]:v[i+m]-v[i];
}
void add(int x,int y,int z){
	n++;v[n][0]=x;v[n][1]=y;v[n][2]=z;
}
void init(){
	for (int i=1;i<=n;i++)
	for (int j=0;j<m;j++)
		a[i][j]=v[i][j];
}
void pivot(int x,int y){
	db d=a[x][y];
	a[x][y]=-1;
	for (int i=0;i<m;i++) a[x][i]/=-d;
	for (int i=0;i<=n;i++)
	if (i!=x&&abs(a[i][y])>eps){
		db d=a[i][y];
		a[i][y]=0;
		for (int j=0;j<=m;j++) a[i][j]+=d*a[x][j];
	}
}
db simplex(){
	int x,y;
	while (1){//得到一个可行解 
		x=y=0;
		for (int i=1;i<=n;i++)
			if (a[i][0]<-eps){x=i;break;}
		if (!x) break;
		for (int i=1;i<m;i++)
			if (a[x][i]>eps) y=i;
		pivot(x,y);
	}
	while (1){
		x=y=0;
		for (int i=1;i<m;i++)
			if (a[0][i]>eps){y=i;break;}
		if (!y) return a[0][0];
		db k=1e10;
		for (int i=1;i<=n;i++)
			if (a[i][y]<-eps&&-a[i][0]/a[i][y]<k)
				k=-a[i][0]/a[i][y],x=i;
		if (!x) return 1e9;
		pivot(x,y);
	}
}
int main()
{
	freopen("starc.in","r",stdin);
	freopen("starc.out","w",stdout);
	scanf("%d%d",&n,&M);
	for (int i=1;i<=n;i++){
		scanf("%s",s);
		for (int j=0;j<m*2;j++)
			scanf("%d",&v[i][j]);
		gete(s[0]=='J',v[i]);
	}
	add(100,-1,0);
	add(100,0,-1);
	add(-1,100,0);
	add(0,100,-1);
	add(-1,0,100);
	add(0,-1,100);
	while (M--){
		int v[6];
		for (int i=0;i<m*2;i++) scanf("%d",&v[i]);
		init();
		for (int i=0;i<m;i++) a[0][i]=v[i]-v[i+m];
		if (simplex()<-eps){puts("B");continue;}
		init();
		for (int i=0;i<m;i++) a[0][i]=v[i+m]-v[i];
		if (simplex()<-eps){puts("J");continue;}
		puts("U");
	}
	return 0;
}