首页 > ACM题库 > HDU-杭电 > HDU 4079-Happy Telephones-计算几何-[解题报告]HOJ
2015
04-16

HDU 4079-Happy Telephones-计算几何-[解题报告]HOJ

Happy Telephones

问题描述 :

In the land of Eden, all phone conversations are happy ones. People complaining on the phone are immediately put in jail. To enforce this law, the police taps all phone conversations.
The police wants to hire the approriate number of operators to listen to all conversations in a given period of time. Unfortunately, each of their operators can listen to one conversation only before needing a really long break to rest from the effort.
As a contractor of the police department, you have been asked to provide a program capable of determining the required number of operators. If the program does not work correctly, you will be put in jail as well, along with all the unhappy complainers. Do you really want to end up there?
Routing

输入:

Each test case starts with two integers denoting the number of phone calls N (1 <= N < 10 000) and the number of intervals M (1 <= M < 100). This is followed by N lines describing the telephone calls, each one consisting of four integers Source, Destination, Start and Duration. Source and Destination identify the pair of telephone numbers establishing the connection (0 <= Source, Destination <= 10 000 000). Start and Duration are the start time and duration of the call in seconds (1 <= Duration <= 10 000 and Start >= 0). You can safely assume that the sum of Start and Duration fits into a 32-bit signed integer.
Afterwards follow M lines containing the time intervals the police are interested in, each on described by two integers Start and Duration, in the same format and with the same meaning and constraints as those in the telephone calls. The last test case is represented by N = M = 0 and must not be processed.

输出:

Each test case starts with two integers denoting the number of phone calls N (1 <= N < 10 000) and the number of intervals M (1 <= M < 100). This is followed by N lines describing the telephone calls, each one consisting of four integers Source, Destination, Start and Duration. Source and Destination identify the pair of telephone numbers establishing the connection (0 <= Source, Destination <= 10 000 000). Start and Duration are the start time and duration of the call in seconds (1 <= Duration <= 10 000 and Start >= 0). You can safely assume that the sum of Start and Duration fits into a 32-bit signed integer.
Afterwards follow M lines containing the time intervals the police are interested in, each on described by two integers Start and Duration, in the same format and with the same meaning and constraints as those in the telephone calls. The last test case is represented by N = M = 0 and must not be processed.

样例输入:

3 2
3 4 2 5
1 2 0 10
6 5 5 8
0 6
8 2
1 2
8 9 0 10
9 1
10 1
0 0

样例输出:

3
2
1
0

点击打开链接

/*

hdu 4079 简单题
只要判断两条直线有交点就可以了
即所感兴趣的时间段的终点大于通话的起点
并且感兴趣时间段的起点小于通话的终点
(这是为了防止出现持续时间为1的情况)

By:ACY
2013-05-04
*/

#include"stdio.h"
#include"string.h"
#define N 10002
struct node
{
    int x,y;
}A[N];
int main()
{
    int i,j,k;
    int n,m;
    int s,d,x,y;
    while(scanf("%d%d",&n,&m),n||m)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&s,&d); 
			scanf("%d%d",&x,&y);
            A[i].x=x;
			A[i].y=x+y;
        }
        for(i=0;i<m;i++)
         {
            scanf("%d%d",&x,&y);
			y=x+y;
            for(k=0,j=0;j<n;j++)
              {
                  if(A[j].y>x&&A[j].x<y)
                       k++;
              }
            printf("%d\n",k);
         }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yangyafeiac/article/details/8882635


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。