/* * Solution for the "Brickwork" problem. * * The problem asks us to determine if a given set of rectangular bricks perfectly * tiles a larger rectangle with no gaps or overlaps. * * My approach is based on two key observations and checks: * * 1. The Area Check: * A necessary condition for a perfect tiling is that the sum of the areas of * all the individual bricks must be equal to the area of the overall bounding * box that encloses all bricks. * - If Sum(Area_brick) == Area_bounding_box, it can be shown that this implies * there are no gaps and no overlaps. This is because any overlap would * necessitate a corresponding gap of equal area to keep the total area sum * consistent. * - Therefore, this single area check is sufficient to prove that the bricks * perfectly tile the region defined by their bounding box. * * 2. The Shape Check (Corner Count Method): * The area check confirms that the bricks tile the bounding box region, but we * still need to confirm that the shape formed is a single, simple rectangle. * This is where the corner count method comes in, based on the principle of * 2D difference arrays. * - For each brick, we treat its four corners as points in a grid and modify * counts at these points: * +1 at the bottom-left (x, y) * -1 at the bottom-right (x+w, y) * -1 at the top-left (x, y+h) * +1 at the top-right (x+w, y+h) * - We use a map to store the sum of these values for every unique corner point. * - If the bricks form a perfect, single rectangle, all the internal corners * where multiple bricks meet will have their values cancel out to zero. * - The only points with a non-zero sum will be the four corners of the final, * large rectangle. Specifically: * - The bottom-left corner of the bounding box should have a sum of +1. * - The top-right corner should have a sum of +1. * - The bottom-right and top-left corners should have sums of -1. * * Implementation Details: * - Coordinates and dimensions can be large, so `long long` is used. * - The total area can exceed the capacity of a 64-bit integer, so `__int128_t` * is used for area calculations. * - A `std::map` stores the corner counts, leading to an overall time * complexity of O(N log N), which is efficient enough for the given constraints. */ #include #include #include #include // Define a type for coordinates to handle large values using coord_t = long long; // Define a type for area, which needs to be 128-bit to avoid overflow using area_t = __int128_t; int main() { // Use fast I/O std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int n; std::cin >> n; area_t total_brick_area = 0; // Initialize bounding box coordinates. // min is initialized to a very large value, max to a small one. coord_t min_x = 2000000007LL, min_y = 2000000007LL; coord_t max_x = 0, max_y = 0; // A map from a point (pair of coordinates) to its accumulated count std::map, int> counts; for (int i = 0; i < n; ++i) { coord_t x, y, w, h; std::cin >> x >> y >> w >> h; // Sum up the individual brick areas total_brick_area += (area_t)w * h; // Update the overall bounding box min_x = std::min(min_x, x); min_y = std::min(min_y, y); max_x = std::max(max_x, x + w); max_y = std::max(max_y, y + h); // Update the corner counts counts[{x, y}]++; counts[{x + w, y}]--; counts[{x, y + h}]--; counts[{x + w, y + h}]++; } // --- CHECK 1: Area Verification --- // The total area of bricks must match the area of their bounding box. // Note: Since n>=1 and w,h>=1, total_brick_area will be positive. // If the areas match, bounding_box_area must also be positive, which implies // max_x > min_x and max_y > min_y, so the box is not degenerate. area_t bounding_box_area = (area_t)(max_x - min_x) * (max_y - min_y); if (total_brick_area != bounding_box_area) { std::cout << "no\n"; return 0; } // --- CHECK 2: Shape Verification using Corner Counts --- // Count how many points have a non-zero final count. int non_zero_count = 0; for (const auto& pair : counts) { if (pair.second != 0) { non_zero_count++; } } // For a perfect rectangle, exactly 4 corner points should have non-zero counts. if (non_zero_count != 4) { std::cout << "no\n"; return 0; } // Verify that the 4 non-zero points are the bounding box corners with correct values. // map::count() checks for key existence, map::at() retrieves the value. if (counts.count({min_x, min_y}) == 0 || counts.at({min_x, min_y}) != 1) { std::cout << "no\n"; return 0; } if (counts.count({max_x, max_y}) == 0 || counts.at({max_x, max_y}) != 1) { std::cout << "no\n"; return 0; } if (counts.count({min_x, max_y}) == 0 || counts.at({min_x, max_y}) != -1) { std::cout << "no\n"; return 0; } if (counts.count({max_x, min_y}) == 0 || counts.at({max_x, min_y}) != -1) { std::cout << "no\n"; return 0; } // If all checks passed, the brickwork is a perfect wall. std::cout << "yes\n"; return 0; }