White Sheet
A white sheet of paper lies on a table. Then two black sheets are placed on the table. All sheets are rectangles with sides parallel to the sides of the table.
Determine whether some part of the white sheet can still be seen from above. A part can be seen if there is a point that lies in the white sheet (its border included) and strictly outside both black sheets.
Constraints:
- \(0 \le x_1 < x_2 \le 10^6\), \(0 \le y_1 < y_2 \le 10^6\), and the same for the black sheets.
Input:
- First line: four integers \(x_1, y_1, x_2, y_2\) — the bottom-left and the top-right corners of the white sheet.
- Second line: four integers \(x_3, y_3, x_4, y_4\) — the first black sheet.
- Third line: four integers \(x_5, y_5, x_6, y_6\) — the second black sheet.
Output:
YESif a part of the white sheet can be seen, andNOotherwise.
Examples:
Input:
2 2 4 4
1 1 3 5
3 1 5 5
Output:
NO
(The white sheet is fully covered by the black sheets.)
Input:
3 3 7 5
0 0 4 6
0 0 7 4
Output:
YES
(For example, the point \((6.5, 4.5)\) can be seen.)
Solution
The white sheet can be seen exactly when the black sheets do not cover all of its area.
- If a part of the white sheet with positive area is not covered, its points can be seen.
- If the uncovered part has zero area, it consists only of segments and points on the borders of the black sheets. Such points are not strictly outside the black sheets, so they cannot be seen.
So we compute the covered area of the white sheet and compare it with the area of the white sheet.
The covered area is the area of the union of \(W \cap B_1\) and \(W \cap B_2\), where \(W\) is the white sheet and \(B_1, B_2\) are the black sheets. When we add the two areas, the part covered by both black sheets is counted twice, so we subtract it once:
\[ \text{covered} = |W \cap B_1| + |W \cap B_2| - |W \cap B_1 \cap B_2| \]
We compute every intersection with the functions from the lesson. \(W \cap B_1 \cap B_2\) is the intersection of the rectangle \(W \cap B_1\) with \(B_2\).
The areas reach \(10^{12}\), so the coordinates and the areas use long long.
#include <algorithm>
#include <iostream>
using namespace std;
struct Point {
long long x;
long long y;
};
struct Rectangle {
Point bottom_left;
Point top_right;
};
long long area(Rectangle r) {
long long width = r.top_right.x - r.bottom_left.x;
long long height = r.top_right.y - r.bottom_left.y;
return width * height;
}
bool rectangles_intersect(Rectangle a, Rectangle b) {
bool separated_x = a.top_right.x <= b.bottom_left.x ||
b.top_right.x <= a.bottom_left.x;
bool separated_y = a.top_right.y <= b.bottom_left.y ||
b.top_right.y <= a.bottom_left.y;
return !separated_x && !separated_y;
}
Rectangle rectangle_intersection(Rectangle a, Rectangle b) {
Rectangle c;
c.bottom_left.x = max(a.bottom_left.x, b.bottom_left.x);
c.bottom_left.y = max(a.bottom_left.y, b.bottom_left.y);
c.top_right.x = min(a.top_right.x, b.top_right.x);
c.top_right.y = min(a.top_right.y, b.top_right.y);
return c;
}
Rectangle read_rectangle() {
Rectangle r;
cin >> r.bottom_left.x >> r.bottom_left.y >> r.top_right.x >> r.top_right.y;
return r;
}
int main() {
Rectangle white = read_rectangle();
Rectangle black1 = read_rectangle();
Rectangle black2 = read_rectangle();
long long covered = 0;
if (rectangles_intersect(white, black1)) {
Rectangle part1 = rectangle_intersection(white, black1);
covered += area(part1);
// the part covered by both black sheets is counted twice
if (rectangles_intersect(part1, black2)) {
covered -= area(rectangle_intersection(part1, black2));
}
}
if (rectangles_intersect(white, black2)) {
covered += area(rectangle_intersection(white, black2));
}
if (covered < area(white)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}- Call
rectangle_intersectiononly whenrectangles_intersectreturnstrue. Otherwise the result is not a valid rectangle, and its “area” can be positive although the rectangles do not intersect.