132 lines
3.7 KiB
Zig
132 lines
3.7 KiB
Zig
const std = @import("std");
|
|
|
|
const Point = struct { x: i64, y: i64 };
|
|
|
|
const Tile = enum { RED, GREEN, EMPTY };
|
|
|
|
pub fn main() !void {
|
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
|
|
defer _ = gpa.deinit();
|
|
|
|
var stdin_buffer: [1024]u8 = undefined;
|
|
var stdin_reader = std.fs.File.stdin().reader(&stdin_buffer);
|
|
|
|
const stdin = &stdin_reader.interface;
|
|
|
|
const allocator = gpa.allocator();
|
|
var red_tiles = try std.ArrayList(Point).initCapacity(allocator, 1);
|
|
defer red_tiles.deinit(allocator);
|
|
|
|
while (try stdin.takeDelimiter('\n')) |line| {
|
|
const line_trimmed = std.mem.trim(u8, line, "\n");
|
|
|
|
var it = std.mem.splitScalar(u8, line_trimmed, ',');
|
|
|
|
const x = try std.fmt.parseInt(i64, it.next().?, 10);
|
|
const y = try std.fmt.parseInt(i64, it.next().?, 10);
|
|
|
|
try red_tiles.append(allocator, Point{ .x = x, .y = y });
|
|
}
|
|
|
|
var task1: i64 = 0;
|
|
var task2: i64 = 0;
|
|
|
|
for (red_tiles.items, 0..) |tile1, i| {
|
|
for (red_tiles.items[i + 1 ..]) |tile2| {
|
|
const minx = @min(tile1.x, tile2.x);
|
|
const maxx = @max(tile1.x, tile2.x);
|
|
const miny = @min(tile1.y, tile2.y);
|
|
const maxy = @max(tile1.y, tile2.y);
|
|
const area = (maxx - minx + 1) * (maxy - miny + 1);
|
|
|
|
if (area > task1) {
|
|
task1 = area;
|
|
}
|
|
|
|
if (area <= task2) {
|
|
continue;
|
|
}
|
|
|
|
// Task2
|
|
// Test if they can form a rectangle
|
|
var formable = true;
|
|
|
|
for (red_tiles.items) |tile| {
|
|
if (tile.x < maxx and tile.x > minx and tile.y < maxy and tile.y > miny) {
|
|
formable = false;
|
|
break;
|
|
}
|
|
}
|
|
|
|
const uminx: u64 = @intCast(minx);
|
|
const umaxx: u64 = @intCast(maxx);
|
|
|
|
// Check diagonal
|
|
const dx: f64 = @floatFromInt(maxx - minx);
|
|
const dy: f64 = @floatFromInt(maxy - miny);
|
|
const fminy: f64 = @floatFromInt(miny);
|
|
const m = dy / dx;
|
|
for (0..umaxx - uminx + 1) |ix| {
|
|
const iix: i64 = @intCast(ix + uminx);
|
|
const fix: f64 = @floatFromInt(ix);
|
|
const iiy: i64 = @intFromFloat(fminy + m * fix);
|
|
if (!isPointInPolygon(Point{ .x = iix, .y = iiy }, red_tiles)) {
|
|
formable = false;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (formable) {
|
|
task2 = area;
|
|
}
|
|
}
|
|
}
|
|
|
|
std.debug.print("{d}\n", .{task1});
|
|
std.debug.print("{d}\n", .{task2});
|
|
}
|
|
|
|
fn isPointInPolygon(p: Point, polygon: std.ArrayList(Point)) bool {
|
|
var instersection_count: usize = 0;
|
|
var j = polygon.items.len - 1;
|
|
|
|
for (0..polygon.items.len) |i| {
|
|
const start = polygon.items[i];
|
|
const end = polygon.items[j];
|
|
|
|
const ymin = @min(start.y, end.y);
|
|
const ymax = @max(start.y, end.y);
|
|
|
|
// Horiztonal
|
|
if (ymin == ymax) {
|
|
const xmin = @min(start.x, end.x);
|
|
const xmax = @max(start.x, end.x);
|
|
|
|
if (p.y == ymin and p.x <= xmax and p.x >= xmin) {
|
|
return true;
|
|
}
|
|
}
|
|
// Vertical
|
|
else {
|
|
const xedge = start.x;
|
|
|
|
if (p.y > ymax or p.y < ymin) {
|
|
continue;
|
|
}
|
|
|
|
// On edge
|
|
if (p.x == xedge and p.y <= ymax and p.y >= ymin) {
|
|
return true;
|
|
}
|
|
|
|
if (p.y >= ymin and p.y < ymax and p.x > xedge) {
|
|
instersection_count += 1;
|
|
}
|
|
}
|
|
|
|
j = i;
|
|
}
|
|
|
|
return instersection_count % 2 == 1;
|
|
}
|