Problem Description

In this scenario, an event organizer is arranging rectangular carpets within the first quadrant of a Cartesian coordinate system. There are n carpets in total, identfiied by unique IDs from 1 to n. The carpets are laid out sequentially in ascending order of their IDs. Each new carpet is placed parallel to the coordinate axes and covers any area previously occupied by carpets with smaller IDs.

Once the layout is complete, the task is to determine the ID of the topmost carpet covering a specific coordinate point. If the point is located on the boundary or vertices of a carpet, it is considered covered. If no carpet covers the point, the system should indicate that.

Input Specification

The input consists of n + 2 lines:

• The first line contains an integer n, representing the total number of carpets.
• The next n lines describe each carpet. The i+1-th line contains four space-separated integers: a, b, g, and k. These represent the bottom-left coordinates (a, b) of the i-th carpet, and its lengths along the x-axis (g) and y-axis (k).
• The final line contains two integers x and y, representing the coordinates of the query point.

Output Specification

Output a single integer representing the ID of the topmost carpet covering the point (x, y). If the point is not covered by any carpet, output -1.

Algorithmic Strategy

A common pitfall in solving this problem is iterating through the carpets in the order they were laid (from 1 to n). While this would identify all carpets covering the point, it would require tracking the maximum ID found or overwriting the result, which is less efficient than necesary.

The optimal approach is to perform a reverse iteration. By starting from the last carpet (ID n) and moving backwards to the first, the algorithm immediately checks the highest layer first. The first carpet found to contain the coordinates is guaranteed to be the topmost one due to the order of the search. This allows for an early exit as soon as a valid covering is found, optimizing performance.

Code Implementation

The following C++ solution implements the reverse iteration strategy. It uses a structure to store the boundaries of each carpet to simplify the colision detection logic.

#include <cstdio>

// Define a structure to hold the rectangle boundaries
struct Rectangle {
    int left, bottom, right, top;
};

int main() {
    int count;
    if (scanf("%d", &count) != 1) return 0;

    // Array to store carpet data
    Rectangle rugs[10005];

    // Read carpet data and calculate boundaries
    for (int i = 0; i < count; ++i) {
        int a, b, g, k;
        scanf("%d %d %d %d", &a, &b, &g, &k);
        
        rugs[i].left = a;
        rugs[i].bottom = b;
        rugs[i].right = a + g;
        rugs[i].top = b + k;
    }

    int targetX, targetY;
    scanf("%d %d", &targetX, &targetY);

    // Iterate backwards from the last carpet to the first
    for (int i = count - 1; i >= 0; --i) {
        // Check if the point lies within the current rectangle
        if (targetX >= rugs[i].left && targetX <= rugs[i].right &&
            targetY >= rugs[i].bottom && targetY <= rugs[i].top) {
            
            // Output ID (i+1 because array is 0-indexed)
            printf("%d\n", i + 1);
            return 0;
        }
    }

    // If no carpet is found after checking all layers
    printf("-1\n");
    return 0;
}

Sample Inputs and Outputs

Sample Input 1:

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

Sample Output 1:

3

Sample Input 2:

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

Sample Output 2:

-1