首页 > ACM题库 > HDU-杭电 > hdu 2555 人人都能参加第30届校田径运动会了[解题报告]C++
2014
02-10

hdu 2555 人人都能参加第30届校田径运动会了[解题报告]C++

人人都能参加第30届校田径运动会了

问题描述 :

杭州师范大学第29届田径运动会圆满的闭幕了,本届运动会是我校规模最大,参赛人数最多的一次运动会。在两天半时间里,由学生、教工组成的61支代表队共2664名运动员参加了比赛。比赛期间,运动健儿赛出了风格、赛出了水平,共有9人次打破6项校纪录。
我们寝室的4名同学是我班最卖力的啦啦队员,每天都在看台上为班级里的运动员们加油助威,为我班获得精神文明奖立下了汗马功劳。可是遗憾的是,与我校的其他近2万名同学一样,我们自己不能上场表演 :(
于是,我们4名同学为下一届校运会发明了一种人人都能参加的比赛项目:
在地面上有N 个大小不等的长方形陷阱,每个陷阱的周长各不相同,每个参赛者都有一个沙包,闭上眼睛把它扔向地面,如果沙包掉到了某个陷阱里,那么这个参赛者根据这个陷阱的周长长度(如50米),绕跑道跑陷阱的周长长度(如50米),如果沙包没有掉到任何一个陷阱里,那么恭喜你,你跑0米。
有m<20000个同学参加了比赛,为了给跑步跑得最多的三位同学(冠军、亚军、季军)颁发安慰奖,必须给这m个同学的跑的长度按从多到少排序。
如下图一样的坐标系与长方形,这些长方形(陷阱)的四条边都与X轴或Y轴平行,它们之间互不相交,它们的左上角顶点的坐标与右下角顶点的坐标已知,给定一个你扔出去的沙包(看作是一个点)的坐标,可以得到你要跑的距离。(注意,这里的坐标值都不超过10000)

输入:

第一行是两个正整数m<20000,n<100,它表示有m 个同学参加了扔沙包比赛,有n个陷阱。
接下去m行是m个同学扔出去的沙包的坐标,每一行都是两个正整数。
接下去的n行是陷阱的坐标,每行有4个正整数,它们从左到右分别是:陷阱左下角顶点的横坐标的值、陷阱左下角顶点的纵坐标的值,陷阱右上角顶点的横坐标的值、陷阱右上角顶点的纵坐标的值。

输出:

第一行是两个正整数m<20000,n<100,它表示有m 个同学参加了扔沙包比赛,有n个陷阱。
接下去m行是m个同学扔出去的沙包的坐标,每一行都是两个正整数。
接下去的n行是陷阱的坐标,每行有4个正整数,它们从左到右分别是:陷阱左下角顶点的横坐标的值、陷阱左下角顶点的纵坐标的值,陷阱右上角顶点的横坐标的值、陷阱右上角顶点的纵坐标的值。

样例输入:

5 3
15 27
32 93
22 3
98 4
65 23
22 65 100 76
2 5 7 9
54 6 94 24

样例输出:

116
0
0
0
0

2011-12-29 22:32:38

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2555

题意:中文。不多解释。

mark:此题真是坑爹。数据里有多个矩形覆盖一个点的情况- -。。。如果有这种情况,就算前一个矩形的周长。。。

另外,在矩形边上也算是包含在陷阱内。

代码:

# include <stdio.h>
# include <string.h>
# include <stdlib.h>


typedef struct point{
    int x, y ;
}point ;


point pt[20010] ;
int a[110][4] ;
int dist[20010] ;


int cmp(const void *a, const void *b)
{
    return *(int*)b - *(int*)a ;
}


int main ()
{
    int n, m, i, j ;
    int u, l, r, d ;
    
    while (~scanf ("%d%d", &n, &m))
    {
        memset (dist, 0, sizeof(dist)) ;
        for (i = 0 ; i < n ; i++)
            scanf ("%d%d", &pt[i].x, &pt[i].y) ;
        
        for (i = 0 ; i < m ; i++)
            scanf ("%d%d%d%d", &a[i][0], &a[i][1], &a[i][2], &a[i][3]) ;
        for (i = 0 ; i < n ; i++)
        {
            dist[i] = 0 ;
            for (j = 0 ; j < m ; j++)
            {
                if (pt[i].x >= a[j][0] && pt[i].x <= a[j][2] &&
                    pt[i].y >= a[j][1] && pt[i].y <= a[j][3])
                {
                    dist[i] = (a[j][2]-a[j][0]+a[j][3]-a[j][1]) * 2 ;
                    break ;
                }
            }
        }
        /*
        for (i = 0 ; i < m ; i++)
        {
            scanf ("%d%d%d%d", &l, &u, &r, &d) ;
            for (j = 0 ; j < n ; j++)
            {
                if (pt[j].x > l && pt[j].x < r &&
                    pt[j].y > u && pt[j].y < d)
                {
                    dist[j] = ((r-l)+(d-u))*2 ;
                }
            }
        }*/
        qsort (dist, n, 4, cmp) ;
        for (i = 0 ;i < n ; i++)
            printf ("%d\n", dist[i]) ;
    }
    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/07/2315404.html