首页 > ACM题库 > HDU-杭电 > HDU 3425-Coverage[解题报告]HOJ
2014
03-23

HDU 3425-Coverage[解题报告]HOJ

Coverage

问题描述 :

A cell phone user is travelling along a line segment with end points having integer coordinates. In order for the user to have cell phone coverage, it must be within the transmission radius of some transmission tower. As the user travels along the path, cell phone coverage may be gained (or lost) as the user moves inside the radius of some tower (or outside of the radii of all towers). Given the location of up to 100 towers and their transmission radii, you are to compute the percentage of cell phone coverage the user has
along the specified path. The (x,y) coordinates are integers between -100 and 100, inclusive, and the tower radii are integers between 1 and 100, inclusive.

输入:

Your program will be given a sequence of configurations, one per line, of the form: N C0X C0Y C1X C1Y T1X T1Y T1R T2X T2Y T2R … Here, N is the number of towers, (C0X,C0Y) is the start of path of the cell phone user,
(C1X,C1Y) is the end of the path, (TkX,TkY) is the position of the kth tower, and TkR is its transmission radius. The start and end points of the paths are distinct. The last problem is terminated by the line 0

输出:

Your program will be given a sequence of configurations, one per line, of the form: N C0X C0Y C1X C1Y T1X T1Y T1R T2X T2Y T2R … Here, N is the number of towers, (C0X,C0Y) is the start of path of the cell phone user,
(C1X,C1Y) is the end of the path, (TkX,TkY) is the position of the kth tower, and TkR is its transmission radius. The start and end points of the paths are distinct. The last problem is terminated by the line 0

样例输入:

3 0 0 100 0 0 0 10 5 0 10 15 0 10
1 0 0 100 0 40 10 50
0

样例输出:

25.00
88.99

/* Created Time: Saturday, November 09, 2013 PM10:39:09 CST */
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1010;
double x[N],y[N],d[N];
int main() {
    int cas,n;
    scanf("%d",&cas);
    while(cas--) {
        scanf("%d",&n);
        for (int i = 0; i < n; i ++)
            scanf("%lf%lf",&x[i],&y[i]);
        sort(y,y+n);
        sort(x,x+n);
        int tot = 0;
        for (int i = 2; i < n; i ++)
            d[tot++] = x[i]-x[i-2];
        d[tot++] = x[1]-x[0];
        d[tot++] = x[n-1]-x[n-2];
        sort(d,d+n);
        double ans = 0;
        for (int i = 0; i < n; i ++)
            ans += y[i]*d[i];
        printf("%.1f\n",ans/2);
    }
    return 0;
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!