/**********************************************************************************/
/* 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;
} |
求解 
