[USACO 2010 Mar G]StarCowraft

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

* 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$

* 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.

#include<bits/stdc++.h> using namespace std; const int N=400; const double eps=1e-10; struct P{ double x,y; P(){x=y=0;} P(double _x,double _y){x=_x,y=_y;} P operator-(const P&a)const{return P(x-a.x,y-a.y);} P operator+(const P&a)const{return P(x+a.x,y+a.y);} P operator*(double a)const{return P(x*a,y*a);} }p[N],a[N]; struct L{ P p,v;double a; L(){} L(P _p,P _v){p=_p,v=_v;} bool operator<(const L&b)const{return a<b.a;} void cal(){a=atan2(v.y,v.x);} }line[N],q[N]; int n,m,cl,h,t; inline double cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;} inline void newL(const P&a,const P&b){line[++cl]=L(a,b-a);} inline bool left(const P&p,const L&l){return cross(l.v,p-l.p)>0;} inline P pos(const L&a,const L&b){ P x=a.p-b.p;double t=cross(b.v,x)/cross(a.v,b.v); return a.p+a.v*t; } inline void halfplane(){ for(int i=1;i<=cl;i++)line[i].cal(); sort(line+1,line+cl+1); h=t=1; q[1]=line[1]; for(int i=2;i<=cl;i++){ while(h<t&&!left(p[t-1],line[i]))t--; while(h<t&&!left(p[h],line[i]))h++; if(fabs(cross(q[t].v,line[i].v))<eps)q[t]=left(q[t].p,line[i])?q[t]:line[i];else q[++t]=line[i]; if(h<t)p[t-1]=pos(q[t],q[t-1]); } while(h<t&&!left(p[t-1],q[h]))t--; p[t]=pos(q[t],q[h]); } int main(){ newL(P(0,0),P(100,1)); newL(P(100,0),P(100,100)); newL(P(1,100),P(0,0)); newL(P(100,100),P(0,100)); newL(P(0.01,100),P(0.01,0)); newL(P(0,0.01),P(100,0.01)); scanf("%d%d",&n,&m); while(n--){ char ch[5];int a,b,c,d,e,f; scanf("%s",ch); if(ch[0]=='J')scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f); else scanf("%d%d%d%d%d%d",&d,&e,&f,&a,&b,&c); a-=d,b-=e,c-=f; if(!a&&!b)continue; if(b){ P A=P(0,-1.0*c/b),B=P(100,(-100.0*a-c)/b),C=A;C.y+=1; if(C.x*a+C.y*b+c>0)newL(A,B);else newL(B,A); }else{ P A=P(-1.0*c/a,0),B=P(-1.0*c/a,100),C=A;C.x-=1; if(C.x*a+C.y*b+c>0)newL(A,B);else newL(B,A); } } halfplane(); while(m--){ int a,b,c,d,e,f; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f); a-=d,b-=e,c-=f; int flag=0; for(int i=h;i<=t;i++){ double tmp=p[i].x*a+p[i].y*b+c; if(tmp>-eps)flag|=1; if(tmp<eps)flag|=2; } if(flag==1)puts("J"); else if(flag==2)puts("B"); else puts("U"); } return 0; }

详情