题目描述
A crane is a wonderful tool for putting up a building. It makes the job go very quickly. When the building must go up even faster, more than one crane can be used. However, when there are too many cranes working on the same building, it can get dangerous. As the cranes spins around, it can bump into another crane if the operator is not careful. Such an accident could cause the cranes to fall over, possibly causing major damage. Therefore, safety regulations require cranes to be spaced far enough apart so that it is impossible for any part of a crane to touch any part of any other crane. Unfortunately, these regulations limit the number of cranes that can be used on the construction site, slowing down the pace of construction. Your task is to place the cranes on the construction site while respecting the safety regulations.
The construction site is laid out as a square grid. Several places on the grid have been marked as possible crane locations. The arm of each crane has a certain length r, and can rotate around the location of the crane. The crane covers the entire area that is no more than r units away from the location of the crane. You are to place the cranes to maximize the total area covered by all the cranes.
输入
The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer C, the number of possible locations where a crane could be placed. There will be no more than 15 such locations. Each of the following C lines contains three integers x, y, and r, all between -10 000 and 10 000 inclusive. The first two integers are the grid coordinates of the location, and the third integer is the length of the arm of the crane that can be placed at that location.
输出
For each test case, find the maximum area A that can be covered by cranes, and output a line containing a single integer B such that A = B × π .
样例输入
1
3
0 0 4
5 0 4
-5 0 4
样例输出
32
参考代码
#include <stdio.h>
int x[20];
int y[20];
int r[20];
int dsq(int i, int j)
{
return i*i + j*j;
}
int hits(int i, int j)
{
return dsq(x[i]-x[j], y[i]-y[j]) <= dsq(r[i]+r[j],0);
}
main()
{
int CASES;
scanf("%d", &CASES);
while(CASES--)
{
int c,i,j,k;
int mx = 0;
scanf("%d", &c);
for (i=0;i<c;i++)
{
scanf("%d %d %d", x+i,y+i, r+i);
}
for (i=0;i<(1<<c);i++)
{
int tota = 0;
for (j=0;j<c;j++)
{
if(!(i & (1<<j))) continue;
tota += r[j]*r[j];
for (k=0;k<c;k++)
{
if(j==k) continue;
if(!(i & (1<<k))) continue;
if(hits(j,k)) goto blah;
}
}
if(tota > mx) mx = tota;
blah:;
}
printf("%dn", mx);
}
}
解析
暂无
