Harder today.
Record the in-edge and out-edge directions of all points. For the point where x is the lowest and y is relatively the lowest, we can ensure that it must be a convex Angle. Therefore, based on its in-edge and out-edge, we can determine whether the drawing process of all edges is clockwise or counterclockwise.
Two checks were conducted successively.
For the two points of the defined rectangle, the directions of their incoming and outgoing edges were checked. It was determined whether the corner was convex or concave based on whether the drawing was clockwise, and it was judge whether it was valid based on the position of the defined points in the rectangle (topleft/bottomleft/topright/bottomright).
If the inspection is passed, conduct an edge cutting inspection, which is relatively simple.
The code is a bit messy, especially not good at naming so many concepts.
pub fn WrapId(comptime cap: usize) type {
return struct {
pub fn next(id: usize) usize {
return (id + 1) % cap;
}
pub fn prev(id: usize) usize {
return (id + cap - 1) % cap;
}
};
}
pub fn part2(input: []const u8) !u64 {
const point_num = 496;
const Direction = enum(u4) {
const BackingVec = packed struct(u4) {
x: i2,
y: i2,
fn cross(in: @This(), out: @This()) i2 {
return in.x * out.y - in.y * out.x;
}
fn turnIsConvex(in: @This(), out: @This(), is_clockwise: bool) bool {
return (in.cross(out) > 0) == is_clockwise;
}
};
left = @bitCast(@as(BackingVec, .{ .x = -1, .y = 0 })),
up = @bitCast(@as(BackingVec, .{ .x = 0, .y = -1 })),
right = @bitCast(@as(BackingVec, .{ .x = 1, .y = 0 })),
down = @bitCast(@as(BackingVec, .{ .x = 0, .y = 1 })),
fn vec(self: @This()) BackingVec {
return @bitCast(@intFromEnum(self));
}
};
const Point = packed struct(u64) {
y: u32,
x: u32,
fn lessThan(_: void, a: @This(), b: @This()) bool {
return @as(u64, @bitCast(a)) < @as(u64, @bitCast(b));
}
fn direction(from: @This(), to: @This()) Direction {
const dx = @as(i33, to.x) - @as(i33, from.x);
const dy = @as(i33, to.y) - @as(i33, from.y);
const backing: Direction.BackingVec = .{
.x = @intCast(std.math.sign(dx)),
.y = @intCast(std.math.sign(dy)),
};
return @enumFromInt(@as(u4, @bitCast(backing)));
}
};
var edges: [point_num]struct {
from_point: Point,
direction: Direction,
} = undefined;
const iw = WrapId(point_num);
var line_it = std.mem.splitScalar(u8, input, '\n');
const first_line = line_it.next().?;
var first_line_it = std.mem.splitScalar(u8, first_line, ',');
edges[0].from_point = .{
.x = try std.fmt.parseUnsigned(u32, first_line_it.next().?, 10),
.y = try std.fmt.parseUnsigned(u32, first_line_it.next().?, 10),
};
var min_point_id: usize = 0;
for (1..point_num) |id| {
const line = line_it.next().?;
var it = std.mem.splitScalar(u8, line, ',');
const point: Point = .{
.x = try std.fmt.parseUnsigned(u32, it.next().?, 10),
.y = try std.fmt.parseUnsigned(u32, it.next().?, 10),
};
edges[id].from_point = point;
if (Point.lessThan({}, point, edges[min_point_id].from_point)) min_point_id = id;
const last_point = edges[iw.prev(id)].from_point;
edges[iw.prev(id)].direction = last_point.direction(point);
}
edges[point_num - 1].direction = edges[point_num - 1].from_point.direction(edges[0].from_point);
const is_clockwise = blk: {
const min_point_vout = edges[min_point_id].direction.vec();
const min_point_vin = edges[iw.prev(min_point_id)].direction.vec();
break :blk min_point_vin.cross(min_point_vout) > 0;
};
var largest_area: u64 = 0;
const Rect = struct {
min_x: u32,
max_x: u32,
min_y: u32,
max_y: u32,
const Corner = enum(u4) {
const BackingVec = packed struct(u4) {
x: i2,
y: i2,
};
topleft = @bitCast(@as(BackingVec, .{ .x = 1, .y = 1 })),
topright = @bitCast(@as(BackingVec, .{ .x = -1, .y = 1 })),
bottomleft = @bitCast(@as(BackingVec, .{ .x = 1, .y = -1 })),
bottomright = @bitCast(@as(BackingVec, .{ .x = -1, .y = -1 })),
fn growVec(self: @This()) BackingVec {
return @bitCast(@intFromEnum(self));
}
fn fromBacking(vec: BackingVec) @This() {
return @enumFromInt(@as(u4, @bitCast(vec)));
}
fn opposite(self: @This()) @This() {
return switch (self) {
.topleft => .bottomright,
.topright => .bottomleft,
.bottomleft => .topright,
.bottomright => .topleft,
};
}
fn validate(
self: @This(),
in_dir: Direction,
out_dir: Direction,
is_cw: bool,
) bool {
const is_convex = (in_dir.vec().cross(out_dir.vec()) > 0) == is_cw;
const growth = self.growVec();
if (is_convex) {
return (growth.x == out_dir.vec().x or growth.x == -in_dir.vec().x) and
(growth.y == out_dir.vec().y or growth.y == -in_dir.vec().y);
} else {
const is_gap_x = (growth.x == out_dir.vec().x or growth.x == -in_dir.vec().x);
const is_gap_y = (growth.y == out_dir.vec().y or growth.y == -in_dir.vec().y);
return !(is_gap_x and is_gap_y);
}
}
};
fn fromDiagonalWithP1Corner(p1: Point, p2: Point) struct { @This(), ?Corner } {
const p1_is_left = p1.x < p2.x;
const p1_is_top = p1.y < p2.y;
return .{
.{
.min_x = if (p1_is_left) p1.x else p2.x,
.max_x = if (p1_is_left) p2.x else p1.x,
.min_y = if (p1_is_top) p1.y else p2.y,
.max_y = if (p1_is_top) p2.y else p1.y,
},
if (p1.x == p2.x or p1.y == p2.y) null else .fromBacking(.{
.x = if (p1_is_left) 1 else -1,
.y = if (p1_is_top) 1 else -1,
}),
};
}
fn area(self: @This()) u64 {
return @as(u64, self.max_x - self.min_x + 1) * @as(u64, self.max_y - self.min_y + 1);
}
fn isEdgeCut(self: @This(), p1: Point, p2: Point) bool {
if (p1.x == p2.x) {
const edge_x = p1.x;
if (edge_x > self.min_x and edge_x < self.max_x) {
const seg_min_y = @min(p1.y, p2.y);
const seg_max_y = @max(p1.y, p2.y);
if (seg_min_y < self.max_y and seg_max_y > self.min_y) {
return true;
}
}
} else if (p1.y == p2.y) {
const edge_y = p1.y;
if (edge_y > self.min_y and edge_y < self.max_y) {
const seg_min_x = @min(p1.x, p2.x);
const seg_max_x = @max(p1.x, p2.x);
if (seg_min_x < self.max_x and seg_max_x > self.min_x) {
return true;
}
}
} else unreachable;
return false;
}
};
for (0..point_num) |i| {
scan_rect: for (i + 1..point_num) |j| {
const p1 = edges[i].from_point;
const p2 = edges[j].from_point;
const rect: Rect, const maybe_p1corner: ?Rect.Corner = Rect.fromDiagonalWithP1Corner(p1, p2);
const area = rect.area();
if (area <= largest_area) continue :scan_rect;
if (maybe_p1corner) |p1corner| {
const p2corner = p1corner.opposite();
if (!p1corner.validate(edges[iw.prev(i)].direction, edges[i].direction, is_clockwise)) continue :scan_rect;
if (!p2corner.validate(edges[iw.prev(j)].direction, edges[j].direction, is_clockwise)) continue :scan_rect;
}
for (0..point_num) |cut_id| {
const cutter1 = edges[cut_id].from_point;
const cutter2 = edges[iw.next(cut_id)].from_point;
if (rect.isEdgeCut(cutter1, cutter2)) continue :scan_rect;
}
largest_area = area;
}
}
return largest_area;
}
.