Repository navigation
Expand file tree
/
Copy pathSolution9.java
More file actions
102 lines (83 loc) · 3.15 KB
/
Copy pathSolution9.java
File metadata and controls
102 lines (83 loc) · 3.15 KB
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
90
91
92
93
94
95
96
97
98
99
100
101
102
public class Solution9 extends Solution {
public Solution9() {
super(9);
}
public static void main(String[] args) {
Solution9 solution = new Solution9();
solution.testPartTwo();
}
@Override
String solvePartOne(String inputData) {
String[] lines = inputData.trim().split("\n");
int n = lines.length;
int[][] pts = new int[n][2];
for (int i = 0; i < n; i++) {
String[] p = lines[i].split(",");
pts[i][0] = Integer.parseInt(p[0]);
pts[i][1] = Integer.parseInt(p[1]);
}
long max = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
long w = Math.abs(pts[i][0] - pts[j][0]) + 1;
long h = Math.abs(pts[i][1] - pts[j][1]) + 1;
max = Math.max(max, w * h);
}
return String.valueOf(max);
}
@Override
String solvePartTwo(String inputData) {
String[] lines = inputData.trim().split("\n");
int n = lines.length;
int[] xs = new int[n];
int[] ys = new int[n];
for (int i = 0; i < n; i++) {
String[] p = lines[i].split(",");
xs[i] = Integer.parseInt(p[0]);
ys[i] = Integer.parseInt(p[1]);
}
long best = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int minX = Math.min(xs[i], xs[j]);
int maxX = Math.max(xs[i], xs[j]);
int minY = Math.min(ys[i], ys[j]);
int maxY = Math.max(ys[i], ys[j]);
// corners must be inside polygon
if (!inside(minX, minY, xs, ys)) continue;
if (!inside(minX, maxY, xs, ys)) continue;
if (!inside(maxX, minY, xs, ys)) continue;
if (!inside(maxX, maxY, xs, ys)) continue;
// rectangle must not intersect polygon edges
if (intersectsPolygon(minX, minY, maxX, maxY, xs, ys)) continue;
long area = (long) (maxX - minX + 1) * (maxY - minY + 1);
best = Math.max(best, area);
}
}
return String.valueOf(best);
}
boolean inside(int x, int y, int[] px, int[] py) {
boolean inside = false;
int n = px.length;
for (int i = 0, j = n - 1; i < n; j = i++) {
if (((py[i] > y) != (py[j] > y)) && (x < (long) (px[j] - px[i]) * (y - py[i]) / (py[j] - py[i]) + px[i])) {
inside = !inside;
}
}
return inside;
}
boolean intersectsPolygon(int lx, int ly, int rx, int ry, int[] px, int[] py) {
int n = px.length;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
int x1 = px[i], y1 = py[i];
int x2 = px[j], y2 = py[j];
if (x1 == x2) {
if (x1 > lx && x1 < rx && Math.max(Math.min(y1, y2), ly) < Math.min(Math.max(y1, y2), ry)) return true;
} else {
if (y1 > ly && y1 < ry && Math.max(Math.min(x1, x2), lx) < Math.min(Math.max(x1, x2), rx)) return true;
}
}
return false;
}
}