＝＝阿里不達轟＝＝

p17johnny

解碼器  Download

ray

/**********************************************************************************/
/*  Problem: d591 "D. 阿里不達轟!!" from 2009 NPSC 國中組初賽           */
/*  Language: CPP (1559 Bytes)                                                    */
/*  Result: AC(328ms, 444KB) judge by this@ZeroJudge                              */
/*  Author: ray0410 at 2011-11-12 21:19:24                                        */
/**********************************************************************************/


#include<iostream>
#include<math.h>
#include<stack>
using namespace std;
struct role
{
   int x;
   int y;
   int r;
};
stack<int>ans;
int bombs,enermys;
role bomb[15],enermy[9];
int hittable[15][9];

void fire(int bombno,int use,int enermylife,int num)
{
     if(use)
     {
       for(int i=0;i<enermys;i++)
       {
          enermylife &= (int)(pow(2,enermys)-1-(pow(2,i)*hittable[bombno][i]));
       }
     }
     bombno++;
     num += use;

     if(enermylife == 0)
     {
       ans.push(num);
     }
     if(enermylife > 0 && bombno < bombs)
     {
       fire(bombno,0,enermylife,num);
       fire(bombno,1,enermylife,num);
     }
}

int main()
{
    int total;
    cin >> total;
    while(total--)
    {
      int i,j,enermylife;
      cin >> bombs >> enermys;
      for(i=0;i<bombs;i++)
        cin >> bomb[i].x >> bomb[i].y >> bomb[i].r;
      for(j=0;j<enermys;j++)
        cin >> enermy[j].x >> enermy[j].y >> enermy[j].r;
      
      for(i=0;i<bombs;i++)
        for(j=0;j<enermys;j++)
          hittable[i][j]=(sqrt(pow(enermy[j].x-bomb[i].x,2)+pow(enermy[j].y-bomb[i].y,2)) <= enermy[j].r+bomb[i].r);
      
      enermylife = (int)pow(2,enermys)-1;
      fire(0,0,enermylife,0);
      fire(0,1,enermylife,0);
      
      int answer = 9999;
      while(ans.size())
      {
        answer = min(ans.top(),answer);
        ans.pop();
      }
      if(answer == 9999)
        cout << "Impossible" << endl;
      else
        cout << answer << endl;
    }
    return 0;
}

p17johnny

   求解