注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

USACO[Elite 2010 March Competition/gold]starc  

2010-04-27 14:34:07|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

}

 

  评论这张
 
阅读(721)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018