CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Help me! Solve for diffcult probem

1. Junior Member
Join Date
Dec 2015
Posts
3

## Help me! Solve for diffcult probem

Mr.David is planning a business trip to the island of Manhattan where he has arranged meetings with buyers at their offices. He wants to stay in a hotel that is not far from their offices. Assume that the streets on the island of Manhattan are given as a grid layout in the plane where each cell is a unit square. See figures below.

Assume also that there are N hotels and M offices of buyers at grid points.

1. N hotels are denoted by H1,…,HN, and Hi=(j,k) is located at the grid point of the j-th row and the k-th column.
2. M offices are denoted by O1,…,OM, and Oi=(j,k) is located at the grid point of the j-th row and the k-th column

The distance between two grid points, p=(i,j) and q=(k,l), is defined by their L8 distance (Chebyshev distance), that is, d8 (p,q)=max{|i - k|, |j - l|}. (|i| is the absolute value of i.) For example, there are two offices and four hotels in Figure 1. Hotel H2=(2,3) is at distance 1 from O2=(3,4) while the other three hotels H1,H3,H4 are all at distance 2 from O2. Given two distinct hotels, H and H’, if we have d(H,Oi) < d(H’,Oi) for all i=1,…M, hotel H is said to dominate hotel H’.

In Figure 1, if we compare hotels H1 and 2, we have d8 (H2,O1) < d8 (H1,O1) and d8 (H2,O2) < d8 (H1,O2), and therefore hotel H2 dominates hotel H1.
In Figure 2, we have d8 (H2,O1) < d8 (H3,O1),d8 (H2,O2) < d8 (H3,O2),d8 (H2,O3) < d8 (H3,O3), and therefore hotel H2 dominates hotel H3. For hotels H1 and H3,

we have d8 (H1,O2 )= d8 (H3,O2 )=5, and therefore they do not dominate each other.

Write a program that given N hotels and M offices, outputs all hotels that are not dominated by any other hotels.

Time Limit: 4 seconds for 30 cases. (If your program exceeds this time limit, the answers that have been already printed are ignored and the score becomes 0. So, it may be better to print a wrong answer when a specific test case might cause your program to exceed the time limit. One guide for the time limit excess would be the size of the input.)

[INPUT]
There can be more than one test case in the input file. The first line has T, the number of test cases. Then the totally T test cases are provided in the following lines (1<=T<=30).

In each test case, the first line has two integers N and M, the numbers of hotels and offices.

In each of the following N lines, two integers A and B are given, where 1<=A,B<=1024.

Here A and B represent the location of a hotel at the grid point of the A-th row and the B-th column.

After then, in each of the following M lines, two integers A and B are given, where 1<=A,B<=1024.

Here A and B represent the location of an offices at the grid point of the A-th row and the B-th column.

Hotels and offices are given in increasing order of their indices: H1,…,HN followed by O1,…,OM. The locations of hotels and offices are all distinct

[OUTPUT]
Each test case contains two lines. For the T-th test case, “Case #T” is printed in the first line. The second line contains the list of indices of hotels, sorted in increasing order, that are not dominated by any other hotels.

[I/O Example]
Input

2 ? There are 2 test cases
4 2 ? Starting Case 1
1 5
2 3
3 6
5 2
1 2
3 4
10 3 ? Starting Case 2
6 2
5 4
6 5
2 4
3 2
4 1
7 3
6 6
1 7
4 7
5 3
1 1
2 6

?Output
Case #1
2
Case #2
1 2 4 5 6 9 10

2. Banned
Join Date
Jun 2015
Posts
208

## Re: Help me! Solve for diffcult probem

For starters, please post the link to the original problem and explain what you find difficult.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•