USACO[Elite 2010 March Competition/gold]starc

恩,星际很好玩,上周就和高一以及高二竞赛班的同学玩了一天(不过我很菜)。

当然,我们玩游戏是为了对这道题了解更加深入。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;

}

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注