pub fn day09(input: &str) -> (u64, u64) {
    let mut part1 = 0;
    let mut part2 = 0;
    let mut squares = Vec::new();
    for line in input.trim().lines() {
        let (x, y) = line.split_once(',').unwrap();
        squares.push([x.parse::<u64>().unwrap(), y.parse::<u64>().unwrap()]);
    }

    let mut chunks = squares.chunks_exact(2).peekable();
    let mut lines = Vec::new();
    let peek = chunks.peek().unwrap();
    // dir is true if scanning vertically, false if horizontally
    let dir = peek[0][1] == peek[1][1];
    if !dir {
        debug_assert_eq!(peek[0][0], peek[1][0]);
    }

    // Each line is a tuple where .0 is the index in the scan direction and .1 is the pair of end
    // points for a line perpendicular to the scan direction
    for line in chunks {
        lines.push((
            line[0][dir as usize],
            [line[0][!dir as usize], line[1][!dir as usize]],
        ));
    }
    lines.sort();

    // rot is true if field 0 being less than field 1 enters the shape, false for exiting
    let rot = lines[0].1[0] < lines[0].1[1];

    for idx_1 in 0..squares.len() - 1 {
        'o: for idx_2 in (idx_1 + 1)..squares.len() {
            let s1 = squares[idx_1];
            let s2 = squares[idx_2];
            let area = (s1[0].abs_diff(s2[0]) + 1) * (s1[1].abs_diff(s2[1]) + 1);
            part1 = std::cmp::max(part1, area);

            if area <= part2 {
                continue;
            }
            // Think of "up" as the direction the scan line travels
            let floor = std::cmp::max(s1[dir as usize], s2[dir as usize]);
            let ceil = std::cmp::min(s1[dir as usize], s2[dir as usize]);
            let left_wall = std::cmp::min(s1[!dir as usize], s2[!dir as usize]);
            let right_wall = std::cmp::max(s1[!dir as usize], s2[!dir as usize]);
            let floor_idx = lines.binary_search_by_key(&floor, |(l, _)| *l).unwrap();
            let ceil_idx = lines.binary_search_by_key(&ceil, |(l, _)| *l).unwrap();
  
            // If a line contracts the valid range, check if that contraction intersects the walls,
            // since that necessitates uncolored tiles in the bounding box
            let skip = |line: [u64; 2]| {
                if rot != (line[0] < line[1]) {
                    return (left_wall..right_wall).contains(&line[0])
                        || (left_wall..right_wall).contains(&line[1]);
                }
                false
            };

            for line in &lines[ceil_idx..floor_idx] {
                if skip(line.1) {
                    continue 'o;
                }
            }
            let mut combo_ranges = Vec::new();
            // This `rev` is needed for correctness, although the full input does not seem to care
            // It actually hurts performance a lot :(
            for line in lines[0..=ceil_idx].iter().rev() {
                if skip(line.1) {
                    continue 'o;
                }
                if rot {
                    combo_ranges.push(line.1);
                } else {
                    combo_ranges.push([line.1[1], line.1[0]]);
                }
                combo_ranges = combine_ranges(combo_ranges);
                // If overlapping the target range results in no change of range, then the target
                // range is fully covered and this rectangle is valid
                let mut test_range = combo_ranges.clone();
                test_range.push([left_wall, right_wall]);
                if combo_ranges == combine_ranges(test_range) {
                    part2 = area;
                    continue 'o;
                }
            }
        }
    }
    (part1, part2)
}