记录编号	422291	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Mar10]星牛争霸	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.324 s
提交时间	2017-07-09 14:49:25	内存使用	31.18 MiB

#include<bits/stdc++.h>
#define N 2010
#define eps 1E-10
#define inf 1e10
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,m=3,kk,v[N][6];
double a[N][N];
char s[10];
inline void add(int x,int y,int z){
	v[++n][0]=x;v[n][1]=y;v[n][2]=z;
}
void pivot(int x,int y){
	double d=a[x][y];
	a[x][y]=-1;
  fo(i,0,m-1) a[x][i]/=-d;
	fo(i,0,n) if (i!=x&&abs(a[i][y])>eps){
		double d=a[i][y];  a[i][y]=0;
		fo(j,0,m) a[i][j]+=d*a[x][j];
	}
}
double simplex(){
	int x,y;
	for(x=y=0;;x=y=0){
		fo(i,1,n)	if (a[i][0]<-eps) {x=i;break;} if (!x) break;
		fo(i,1,m)	if (a[x][i]> eps) y=i;
		pivot(x,y);
	}
	for(x=y=0;;x=y=0){
		fo(i,1,m) if (a[0][i]>eps){y=i;break;}
		if (!y) return a[0][0];
		double k=inf;
		fo(i,1,n) if (a[i][y]<-eps&&-a[i][0]/a[i][y]<k) k=-a[i][0]/a[i][y],x=i;
		if (!x) return inf;
		pivot(x,y);
	}
}
int main()
{
	freopen("starc.in","r",stdin);
	freopen("starc.out","w",stdout);
	scanf("%d%d",&n,&kk);
	for (int i=1;i<=n;i++){
		scanf("%s",s);  for (int j=0;j<m*2;j++) scanf("%d",&v[i][j]);
		fo(ll,0,m-1)	v[i][ll]=s[0]=='J'?v[i][ll]-v[i][ll+m]:v[i][ll+m]-v[i][ll];
	}
	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 (kk--){
		int tt[6];
		fo(i,0,m*2-1) scanf("%d",&tt[i]); 
		fo(i,1,n) fo(j,0,m-1) a[i][j]=v[i][j];
		fo(i,0,m-1) a[0][i]=tt[i]-tt[i+m];
		if (simplex()<-eps){putchar('B');continue;}
		fo(i,1,n) fo(j,0,m-1) a[i][j]=v[i][j];
		fo(i,0,m-1) a[0][i]=tt[i+m]-tt[i];
		if (simplex()<-eps){putchar('J');continue;}
		putchar('U');
	}
	return 0;
}