Restaurants
Problem Description:
Looking for a place to rent in New York, Codu wants to stay in a place close to as many restaurants as possible and walk as little as possible to reach them. As he is a vegetarian, and likes only some types of food, there are only a few restaurants that meet his criteria.
For convenience he models the roads as rectangular grid roads and plots the restaurant locations at the intersection of two roads there. To simplify further, he approximates the distance as the number of blocks between two places. Given the maximum distance he wants to walk, he wants to find the most optimal location(from which he can reach the maximum number of restaurants within that distance).
The grid starts at (0,0) at the southwest corner, and goes to (N,0) at the south east corner, and to (N,M) at the north east corner. If two locations the same (maximum)number of restaurants he can walk to, he would prefer to have the southern most location (lowest Y coordinate). If two locations lie on the same southernmost road and have the same (maximum) number of restaurants he can walk to, he would prefer the westernmost location (lowest X coordinate).
Constraints
1 < N,M,K <= 1000
House can’t be in the same block where there exists a restaurant
Input Format
First line contains two integers N, M the number of horizontal and vertical blocks(intervals between roads). The grid is given the coordinates starting with (0,0) on thelower left corner and (N,M) the upper right corner. The next line contains K, the number of restaurants. The next K pairs of integers give the coordinates of the K restaurants. The next line gives the distance he wants to walk (in blocks)
Output
Three integers, first two giving the coordinates of the optimal location and the next integer giving the number of restaurants reachable from that location.
Test Case
Example 1:
Input
4 4
5
1 1
1 2
3 3
4 4
2 4
4
Output
3 1 5
Solution:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct Restaurant {
int x, y;
};
int distance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
int N, M, K;
scanf("%d %d", &N, &M);
scanf("%d", &K);
struct Restaurant restaurants[K];
for (int i = 0; i < K; i++) {
scanf("%d %d", &restaurants[i].x, &restaurants[i].y);
}
int maxDistance;
scanf("%d", &maxDistance);
int maxRestaurants = 0;
int optimalX, optimalY;
for (int x = 0; x <= N; x++) {
for (int y = 0; y <= M; y++) {
int currentRestaurants = 0;
for (int i = 0; i < K; i++) {
if (distance(x, y, restaurants[i].x, restaurants[i].y) <= maxDistance) {
currentRestaurants++;
}
}
if (currentRestaurants > maxRestaurants ||
(currentRestaurants == maxRestaurants && (y < optimalY
|| (y == optimalY && x < optimalX)))) {
maxRestaurants = currentRestaurants;
optimalX = x;
optimalY = y;
}
}
}
printf("%d %d %d\n", optimalX, optimalY, maxRestaurants);
return 0;
}
You can also run it on an online IDE:
Your feedback are always welcome! If you have any doubt you can contact me or leave a comment! Happy Coding !! Cheers!!!
No comments:
Post a Comment