/
FieldReduction.java
89 lines (88 loc) · 3.18 KB
/
FieldReduction.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.util.*;
import java.io.*;
public class FieldReduction {
static PointX[] xVals;
static PointY[] yVals;
static int n;
static int finArea = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(new BufferedReader(new FileReader("reduce.in")));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("reduce.out")));
// remove every set of 3 points O(n^3)
// compute area afterward of remaining points O(n)
// O(n^4)
// three outermost left, three o.m. right, top, bottom
// any combination of any three of these points and calculate
// area
n = scan.nextInt();
xVals = new PointX[n];
yVals = new PointY[n];
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
int y = scan.nextInt();
xVals[i] = new PointX(x, y);
yVals[i] = new PointY(x, y);
}
Arrays.sort(xVals);
Arrays.sort(yVals);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = n - 1; k > n - 5; k--) {
for (int l = n - 1; l > n - 5; l--) {
findCowsAndArea(xVals[k].x, yVals[l].y, xVals[i].x, yVals[j].y, xVals[k].y, yVals[l].x, xVals[i].y, yVals[j].x);
}
}
}
}
pw.println(finArea);
scan.close();
pw.close();
}
public static void findCowsAndArea(int upperX, int upperY, int lowerX, int lowerY, int y2, int x2, int y3, int x3) {
upperX = Math.max(upperX, lowerX);
upperY = Math.max(upperY, lowerY);
lowerX = Math.min(upperX, lowerX);
lowerY = Math.min(upperY, lowerY);
int tempArea = (upperX - lowerX) * (upperY - lowerY);
if (!(upperX < x2 || upperX < x3 || lowerX > x2 || lowerX > x3 || upperY < y2 || upperY < y3 || lowerY > y2 || lowerY > y3)) {
if (upperX == lowerX || upperY == lowerY) {
return;
}
HashSet<Integer> indices = new HashSet<>();
for (int i = 0; i < xVals.length; i++) {
if ((xVals[i].x > upperX || xVals[i].x < lowerX) || (xVals[i].y > upperY || xVals[i].y < lowerY)) {
indices.add(i);
}
}
int len = indices.size();
if (len <= 3 && tempArea < finArea) {
finArea = tempArea;
System.out.println(upperX + " " + upperY + " " + lowerX + " " + lowerY);
}
}
}
static class PointX implements Comparable<PointX> {
int x;
int y;
public PointX(int x2, int y2) {
x = x2;
y = y2;
}
@Override
public int compareTo(PointX other) {
return Integer.compare(this.x, other.x);
}
}
static class PointY implements Comparable<PointY> {
int x;
int y;
public PointY(int x2, int y2) {
x = x2;
y = y2;
}
@Override
public int compareTo(PointY other) {
return Integer.compare(this.y, other.y);
}
}
}