CodingGyan

Rectangle Class: Intersection and Containment

medium Object-Oriented Programming

Problem

A rectangle has its left-bottom corner (X1, Y1) and its right-top corner (X2, Y2), with X1 < X2 and Y1 < Y2. Commands: rect NAME X1 Y1 X2 Y2, area NAME, overlap A B (print the area of the part that both rectangles share; rectangles that only touch at an edge share an area of 0), contains A B (true if B lies completely inside A, edges may touch).

Constraints

  • 1 <= commands <= 100
  • X1 < X2 and Y1 < Y2

Examples

Input

rect a 0 0 4 3
rect b 2 1 6 5
overlap a b

Output

4

Solutions

Best approachTime O(n)Space O(n)

The overlap is found one axis at a time: the shared width is the smaller right edge minus the larger left edge, and the same for the height. A non-positive side means the rectangles do not share any area, including the case when they only touch.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Run the commands.
 * Input   : Command lines.
 * Output  : One line per answer.
 * Approach: Rect class
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A Rect keeps the two corners. Width and height are found from them.
        static class Rect {
            private final long x1, y1, x2, y2;

            Rect(long x1, long y1, long x2, long y2) {
                this.x1 = x1;
                this.y1 = y1;
                this.x2 = x2;
                this.y2 = y2;
            }

            long area() {
                return (x2 - x1) * (y2 - y1);
            }

            // Step 2: The shared part is the rectangle between the larger left and the smaller right (and the same for y).
            // Step 3: If a side is not positive, there is no shared part, so the area is 0.
            long overlapArea(Rect other) {
                long width = Math.min(x2, other.x2) - Math.max(x1, other.x1);
                long height = Math.min(y2, other.y2) - Math.max(y1, other.y1);
                return width > 0 && height > 0 ? width * height : 0;
            }

            boolean contains(Rect other) {
                return x1 <= other.x1 && y1 <= other.y1 && other.x2 <= x2 && other.y2 <= y2;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        java.util.Map<String, Rect> named = new java.util.HashMap<String, Rect>();
        java.util.List<String> out = new java.util.ArrayList<String>();
        for (String line : lines) {
            String[] part = line.split(" ");
            if (part[0].equals("rect")) {
                named.put(part[1], new Rect(Long.parseLong(part[2]), Long.parseLong(part[3]), Long.parseLong(part[4]), Long.parseLong(part[5])));
            } else if (part[0].equals("area")) {
                out.add(String.valueOf(named.get(part[1]).area()));
            } else if (part[0].equals("overlap")) {
                out.add(String.valueOf(named.get(part[1]).overlapArea(named.get(part[2]))));
            } else {
                out.add(String.valueOf(named.get(part[1]).contains(named.get(part[2]))));
            }
        }
        return out.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. Why is the shared area 0 when the rectangles only touch at an edge?
  2. What is different between overlap and contains?

Try these next