恩，星际很好玩，上周就和高一以及高二竞赛班的同学玩了一天（不过我很菜）。
当然，我们玩游戏是为了对这道题了解更加深入。O(∩_∩)O哈哈~。
然后，就是半平面交了。
用已知信息进行半平面交，得出可行域。
然后线性规划。
如果最优都小于零或最差都大于零则判断。
否则不可判断。
CODE:
/*
PROG: starc
LANG: C++
ID: boleyn.2
*/
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-4-27
DESCRIPTION:
TITLE: StarCowraft [Jaehyun Park/KOI 2007, 2010]
CONTENT:
The beta version of StarCowraft II is ready! Farmer John and Bessie
are testing it, trying different strategies in one-on-one battles
against each other’s armies. The goal in StarCowraft II is to defeat
your opponent’s army in a battle.
Each player’s army fights in a battle. An army comprises as many
as three different types of ‘units’ with respective strengths denoted
by constant positive real numbers unknown to the players: cattlebruisers
with strength S1, cow templars with strength S2, and ultracows with
strength S3. The only given bounding information is that no unit
is more than 100 times as strong as any another unit.
An army’s total strength is the sum of the individual strengths of
each of its units. An army that has, among others units, 23
cattlebruisers would gain 23*S1 strength just from the cattlebruisers.
When two opposing armies fight in a battle, the army with a higher
total strength value wins. If the armies have exactly equal strength
values, one of the players randomly wins.
Farmer John and Bessie played N (0 <= N <= 300) “test battles”. In
the i-th test battle, FJ’s army had J1_i cattlebruisers, J2_i cow
templars, and J3_i ultracows (0 <= J1_i + J2_i + J3_i <= 1,000).
Similarly, Bessie’s army had B1_i cattlebruisers, B2_i cow templars,
and B3_i ultracows (0 <= B1_i + B2_i + B3_i <= 1,000). After their
armies fought against each other, FJ and Bessie recorded the winner
as a single ‘victory letter’ V_i: “J” if Farm John won the battle;
“B” if Bessie won.
Although these victory results are the only information that they
have, they hope to predict some of the results of additional battles
if they are given the unit compositions of two opposing armies. For
some battles, though, they know it might not be possible to determine
the winner with certainty.
Given the results of the N test battles that Farmer John and Bessie
already played, write a program that decides the winner (if possible)
for M (1 <= M <= 2,000) new battles.
The results reported for the test battles are correct; there exists
at least one set of strength values which are consistent with the
results.
For purposes of demonstrating the army strength evaluation functions,
consider these test battles fought in a game where we (but neither
FJ nor Bessie) know that S1=9.0, S2=7.0, and S3=4.0:
—- Farmer John —- ——- Bessie —— Battle
J1 J2 J3 J_Strength B1 B2 B3 B_Strength Outcome
6 5 4 105 5 4 7 101 J
5 4 2 81 3 5 5 82 B
9 0 10 121 8 2 7 114 J
These results connote the following deduced results for the reasons
shown:
—- Farmer John —- ——- Bessie —— Battle
J1 J2 J3 J_Strength B1 B2 B3 B_Strength Outcome
6 6 4 112 5 4 7 101 J
FJ’s army is even stronger than in test battle 1
9 0 10 121 8 2 6 110 J
Bessie’s army is even weaker than in test battle 3
PROBLEM NAME: starc
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes a test battle with seven
space-separated items — a victory letter and six
space-separated integer unit counts: V_i, J1_i, J2_i, J3_i,
B1_i, B2_i, and B3_i
* Lines N+2..N+M+1: Line i+N+1 describes a “new battle” using six
space-separated integers: J1_i, J2_i, J3_i, B1_i, B2_i, and
B3_i
SAMPLE INPUT (file starc.in):
3 3
J 6 5 4 5 4 7
B 5 4 2 3 5 5
J 9 0 10 8 2 7
6 6 4 5 4 7
9 0 10 8 2 6
3 4 8 4 4 6
OUTPUT FORMAT:
* Lines 1..M: Line i contains the outcome of the i-th new battle: “J”
if Farmer John definitely wins, “B” if Bessie definitely wins,
and “U” (undecidable) if it is impossible to decide the winner
with the given information.
SAMPLE OUTPUT (file starc.out):
J
J
U
OUTPUT DETAILS:
First two games correspond to the examples in the description. The
result of the last game cannot be determined with only the information
that Farmer John and Bessie currently have. Specifically, both S_1=9.0,
S_2=7.0, S_3=4.0 and S_1=12.0, S_2=20.0, S_3=10.0 are consistent with the
“test battles,” but they give different results when plugged in the third
“new battle.”
*/
#include <stdio.h>
#include <vector>
using namespace std;
#define Point pair<double,double>
#define x first
#define y second
#define P make_pair
#define Polygon vector<Point>
const double MAXRATIO=100;
const double ZERO=1e-10;
int N,M;
Polygon polygon;
char getf(double a,double b,double c,Point p)
{
double f=a*p.x+b*p.y+c;
//printf(“a=%.2f,b=%.2f,c=%.2f\n”,a,b,c);
//printf(“P(%.2f,%.2f)\n”,p.x,p.y);
//printf(“f:%.8f\n”,f);
if (f<-ZERO) return ‘J’;
if (f>ZERO) return ‘B’;
return ‘U’;
}
Point intersection(double a,double b,double c,Point p1,Point p2)
{
double f1=a*p1.x+b*p1.y+c;
double f2=a*p2.x+b*p2.y+c;
return P((f2*p1.x-f1*p2.x)/(f2-f1),(f2*p1.y-f1*p2.y)/(f2-f1));
}
void cut(int a,int b,int c,char f)
{
Polygon get;
for (int i=0;i<polygon.size();i++)
if (getf(a,b,c,polygon[i])==f)
get.push_back(polygon[i]);
else
{
int before,next;
if (i) before=i-1;
else before=polygon.size()-1;
if (i+1!=polygon.size()) next=i+1;
else next=0;
if (getf(a,b,c,polygon[before])==f)
get.push_back(intersection(a,b,c,polygon[before],polygon[i]));
if (getf(a,b,c,polygon[next])==f)
get.push_back(intersection(a,b,c,polygon[i],polygon[next]));
}
polygon.swap(get);
}
char check(int a,int b,int c)
{
bool getJ=false;
bool getB=false;
for (int i=0;i<polygon.size();i++)
{
char f=getf(a,b,c,polygon[i]);
if (f==’U’) return ‘U’;
if (f==’J’) getJ=true;
if (f==’B’) getB=true;
if (getJ&&getB) return ‘U’;
}
if (getJ) return ‘J’;
if (getB) return ‘B’;
}
int main()
{
freopen(“starc.in”,“r”,stdin);
freopen(“starc.out”,“w”,stdout);
scanf(“%d %d\n”,&N,&M);
polygon.push_back(P(1.0/MAXRATIO,1.0/MAXRATIO));
polygon.push_back(P(1.0/MAXRATIO,MAXRATIO));
polygon.push_back(P(MAXRATIO,MAXRATIO));
polygon.push_back(P(MAXRATIO,1.0/MAXRATIO));
cut(-MAXRATIO,1,0,’J’);
cut(1,-MAXRATIO,0,’J’);
for (int i=0;i<N;i++)
{
char f;
int a1,b1,c1,a2,b2,c2;
scanf(“%c %d %d %d %d %d %d\n”,&f,&a1,&b1,&c1,&a2,&b2,&c2);
int a=a2-a1,b=b2-b1,c=c2-c1;
cut(a,b,c,f);
//for (int i=0;i<polygon.size();i++)
// printf(“P(%.2f,%.2f)\n”,polygon[i].x,polygon[i].y);
//printf(“\n”);
}
for (int i=0;i<M;i++)
{
int a1,b1,c1,a2,b2,c2;
scanf(“%d %d %d %d %d %d\n”,&a1,&b1,&c1,&a2,&b2,&c2);
int a=a2-a1,b=b2-b1,c=c2-c1;
printf(“%c\n”,check(a,b,c));
}
fclose(stdin);
fclose(stdout);
return 0;
}
