TCHS-7-1000

Problem Statement

You are given an even number of points in the plane. You want to find a rectangle whose corners have integer coordinates and sides are parallel to the axes, such that at least half of the given points lie in the interior of the rectangle. Return the area of the smallest such rectangle. ("Smallest rectangle" means the rectangle with the smallest area.) Note that if a point lies on the edge of the rectangle, it does not count as being in the interior.

The input is formatted as follows. You are given String[] X and String[] Y. The first thing that you should do is concatenate the elements of X to form a single String. This String contains up to 100 integer numbers without extra leading zeroes, each separated by one or more spaces. The ith number in this String is the x-coordinate of the ith point. Similarly, you should concatenate the elements of Y to form a single String. That String also contains up to 100 integer numbers without extra leading zeroes, each separated by one or more spaces. The ith number in this String is the y-coordinate of the ith point.

Definition

Class:	EnclosingRectangle
Method:	smallestArea
Parameters:	String[], String[]
Returns:	int
Method signature:	int smallestArea(String[] X, String[] Y)
(be sure your method is public)

Notes

-

If a point lies on the edge of a rectangle, it does not count as being in the interior of that rectangle.

Constraints

-

X contains between 1 and 50 elements, inclusive.

-

Each element of X is a String which contains between 0 and 50 characters, inclusive. Each character is a digit ('0'-'9') or a space (' ').

-

The String formed by concatenating the elements of X has no leading or trailing spaces, and consists of a list of integer numbers separated by one or more spaces. Each number in the list is between 0 and 10000, inclusive, and has no extra leading zeroes.

-

Y contains between 1 and 50 elements, inclusive.

-

Each element of Y is a String which contains between 0 and 50 characters, inclusive. Each character is a digit ('0'-'9') or a space (' ').

-

The String formed by concatenating the elements of Y has no leading or trailing spaces, and consists of a list of integer numbers separated by one or more spaces. Each number in the list is between 0 and 10000, inclusive, and has no extra leading zeroes.

-

The number of integers represented in X is the same as the number of integers represented in Y, which is an even number between 2 and 100, inclusive.

-

All points are distinct.

Examples

0)

{ "100 200" }

{ "100 200" }

Returns: 4

We have two points (100,100) and (200,200). One way to enclose at least one point is to have the rectangle with opposite corners at (99,99) and (101,101). The area of this rectangle is 4.

1)

{ "10 11 13 10 11 13" }

{ "5 5 5 15 16 17" }

Returns: 10

We have six points (10,5), (11,5), (13,5), (10,15), (11,16), (13,17). The rectangle with opposite corners at (9,4) and (14,6) encloses the first three points. It turns out that no smaller rectangle can enclose at least three of the six given points. The area of this rectangle is 10.

2)

{ "5 6 6 7 7 8 8 9" }

{ "7 6 8 5 9 6 8 7" }

Returns: 16

These points form a diamond shape

3)

{ "4496 6443 2837 557 4098 1083 3466 1250 6126 ", "3135 7598 9274 9180 5128 741 7625 8316 414 ", "9071 8753 5509 1080 2797 906 3805 698 947 ", "8645 9640 2596 6883 1845 9169 3922 4792 7919 ", "7389 9397 4901 1343 3347 6366 9118 3148 780 ", "4541 9479 483 1174 9615 8900 3067 5397 9879 ", "7440 8948 846 8881 7602 6760 3327 5197 9017 ", "5463 6781 2478 6270 5392 9420 9069 3609 6401 ", "1810 6680 6787 9840 1031 1916 5415 1168 5154 ", "2727 8834 9125 3961 4289 4750 5524 5118 5258 ", "2652 7020 9770 5866 3386 6447 7960 3889 2158 ", "6717" }

{ "6801 8243 9390 2156 5505 5509 3442 6663 1294 ", "9979 1008 5644 7516 5442 5909 4550 2431 2779 ", "419 4744 8155 7800 2944 4169 1633 1464 7353 ", "5365 1548 3073 8596 4461 2540 4664 5057 1870 ", "4782 4028 8003 9175 2592 4520 2420 6955 519 ", "2141 1580 5170 9138 4268 9724 1093 5633 9820 ", "3411 9789 6200 7661 2296 8644 8259 8631 4342 ", "574 530 6664 8812 161 8141 6210 2803 3209 ", "8090 6380 3498 3014 7650 7062 8853 5939 4578 ", "8647 4020 4844 3362 4930 9447 1346 6162 8242 ", "9276 6967 589 6960 5467 8768 9018 8155 3886 ", "7274" }

Returns: 37305252

One hundred points.

4)

{ "5481 3318 5721 9019 ", "1618 9762 1654 2275 ", "5361 307 6833 9456 ", "7473 6088 9685 2725" }

{ "1181 7762 3889 7015 ", " 5445 9063 2510 8229 ", " 4390 6454 9197 708 ", " 2221 9012 2665 8308" }

Returns: 25959465

5)

{ "1242 9594 6816 833 6587 7183 9355 7087 ", " ", "8675 5944 786 3597 1327 9884 7138 8073 ", "", "3017 5468 331 8136" }

{ "1105 7791 7865 8119 ", "9950 8261 5988 1708 ", "1615 5400 487 4837 4712 5777 3819 ", "", "5063 5143 5990 2895 4375", "" }

Returns: 18598707

6)

{ "100", " 200" }

{ "100 2", "00" }

Returns: 4

Remember to concatenate the elements of X and Y first.

import java.util.*;

public class EnclosingRectangle {

	class Pos {
		int x, y;
		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public int smallestArea(String[] X, String[] Y) {
		int[] x = parse(X);
		int[] y = parse(Y);
		int n = x.length;
		int half = n / 2;
		List<Pos> ps = new ArrayList<Pos>();
		for (int i = 0; i < n; i++)
			ps.add(new Pos(x[i], y[i]));
		Comparator<Pos> xPlus = new Comparator<Pos>() {
			public int compare(Pos p1, Pos p2) {
				return p1.x - p2.x;
			}
		};
		Comparator<Pos> yPlus = new Comparator<Pos>() {
			public int compare(Pos p1, Pos p2) {
				return p1.y - p2.y;
			}
		};
		Collections.sort(ps, xPlus);
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++)
			for (int j = i; j < n; j++) {
				int x1 = ps.get(i).x;
				int x2 = ps.get(j).x;
				List<Pos> band = new ArrayList<Pos>();
				for (int k = 0; k < n; k++) {
					Pos p = ps.get(k);
					if (p.x >= x1 && p.x <= x2)
						band.add(p);
				}
				Collections.sort(band, yPlus);
				for (int k = 0; k < band.size()-half+1; k++) {
					int y1 = band.get(k).y;
					int y2 = band.get(k+half-1).y;
					min = Math.min(min, (x2-x1+2)*(y2-y1+2));
				}
			}
		return min;
	}

	private int[] parse(String[] ss) {
		StringBuilder buf = new StringBuilder();
		for (String s : ss)
			buf.append(s);
		StringTokenizer tok = new StringTokenizer(buf.toString());
		int[] cord = new int[tok.countTokens()];
		for (int i = 0; i < cord.length; i++)
			cord[i] = new Integer(tok.nextToken());
		return cord;
	}

}