若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1214: Cranes

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,245

题目描述

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);
    }
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist