Cranes

Cranes

时间: 1ms        内存:128M

描述:

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

提示:

参考答案(内存最优[752]):

#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("%d\n", mx);
    }
}

参考答案(时间最优[0]):

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define MP make_pair
#define A first
#define B second

#define PB push_back
#define FR(i, a, b) for(int i=(a); i<(b); i++)
#define FOR(i, n) FR(i, 0, n)
#define RF(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define ROF(i, n) RF(i, 0, n)
#define EACH(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)

#define MAXN 110000

int lis[MAXN],n,m,ans,del;

int work(int len){
  int pre,cou;
  if(len<0) return 0;
  pre=-(1<<20);
  cou=0;
  FOR(i,n)
    if(lis[i]>pre+len){
      pre=lis[i];
      if(++cou>m) return 0;
    }
  return 1;
}

int main(){
  int ct;
  scanf("%d",&ct);
  while(ct--){
    scanf("%d%d",&m,&n);
    FOR(i,n) scanf("%d",&lis[i]);
    sort(lis,lis+n);
    ans=del=1<<20;
    while(del){
      if(work(ans-del)) ans-=del;
      del/=2;
    }
    printf("%d.%d\n",ans/2,(ans%2==0)?0:5);
  }
  return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

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