Решение задачи UniLecs №64

max_complement.rs

const COORD_BOUND: usize = 100;       //Максимально воможное по модулю значение координат
type CoordBase = i16;                 //Тип координат. Выбирается так, чтобы включал в
type Coord = (CoordBase, CoordBase);  //диапазон [-COORD_BOUND, COORD_BOUND]

struct View2d {                       //Вспомогательная структура для более удобной
    side: usize,                      //индексации
    inner: Vec<usize>,
}

impl View2d {
    fn from_vec(inner: Vec<usize>, side: usize) -> Self {
        View2d { inner, side }
    }
    fn width(&self) -> usize { self.side }
    fn height(&self) -> usize { self.side }
}

use std::ops::{Index, IndexMut};
type Index2 = (usize, usize);

//Реализация индексирования
impl Index<Index2> for View2d {
    type Output = usize;
    fn index(&self, (x, y): Index2) -> &Self::Output {
        &self.inner[x * self.side + y]
    }
}

impl IndexMut<Index2> for View2d {
    fn index_mut(&mut self, (x, y): Index2) -> &mut Self::Output {
        &mut self.inner[x * self.side + y]
    }
}

//---------------------------------------------------------

//Подсчитывает периметр фигуры, заданной координатами
fn figure_perimeter(figure: &View2d) -> usize {
    let mut perimeter: usize = 0;
    for i in 0..figure.width() {
        for j in 0..figure.height() {
            if figure[(i, j)] == 1 {      //Для каждого квадрата
                perimeter += 4            //вклад в периметр фигуры
                    - figure[(i - 1, j)]  //равен 4 минус число
                    - figure[(i + 1, j)]  //соседей
                    - figure[(i, j - 1)]
                    - figure[(i, j + 1)];
            }
        }
    }
    perimeter
}

//Создаёт буфер для более удобного подсчёта периметра
//По краям добавляется по ряду клеток во избежание
//выхода за границы массива при подсчёте периметра
fn make_buffer(squares: &[Index2]) -> View2d {
    let buffer_side = 2*COORD_BOUND + 3;
    let buffer = vec!(0; buffer_side * buffer_side);
    
    let mut buffer = View2d::from_vec(buffer, buffer_side);
    for &point in squares {
        buffer[point] = 1;
    }
    buffer
}

//Подсчитывает размеры ограничивающего прямоугольника
fn calculate_bounds(squares: &[Index2]) -> (usize, usize) {
    use std::usize::{MIN, MAX};
    let mut bounds = (MAX, MAX, MIN, MIN);
    for &(x, y) in squares {
        bounds = (
            bounds.0.min(x),
            bounds.1.min(y),
            bounds.2.max(x),
            bounds.3.max(y));
    }
    ((bounds.2 - bounds.0 + 1) as usize, (bounds.3 - bounds.1 + 1) as usize)
}

fn shift_by((x, y): Coord, shift: CoordBase) -> Index2 {
    ((x + shift) as usize, (y + shift) as usize)
}

//Главная функция, непосредственно решающая задачу
fn calculate_max_complement(squares: &[Coord]) -> usize {
    let shift = (COORD_BOUND + 1) as CoordBase;    //Преобразование массива
    let shifted = squares.into_iter()              //из знакового в беззнаковый
        .map(|&x| shift_by(x, shift))              //(тип Vec поддерживает индексацию
        .collect::<Vec<_>>();                      //только по usize).
    let buffer = make_buffer(&shifted);
    let fig_perim = figure_perimeter(&buffer);     //Считаем периметр

    let (width, height) = calculate_bounds(&shifted);  //Считаем разницу
    let bounds_perim = 2 * (width + height);           //между периметрами граничного
    let perim_delta = fig_perim - bounds_perim;        //прямоугольника и исходной
    let delta = perim_delta / 2;                       //фигуры

    let mut complement = width*height - squares.len();  //Для начала нужно заполнить дырки в фигуре
    let (mut bigger, mut smaller) = (width.max(height), width.min(height));
    for _ in 0..delta {
        if bigger < smaller {
            std::mem::swap(&mut bigger, &mut smaller);
        }
        complement += bigger;    //Приписываем ряд к бОльшей стороне
        smaller += 1;            //и учитывем, что это увеличивает меньшую
    }
    complement
}

//----------------------------------------------------------

fn main() {
    let arr = [
        (1, 1),
        (2, 1),
        (2, 2),
    ];
    assert_eq!(calculate_max_complement(&arr), 1);
    let arr = [
        (0, 0),
        (0, 1),
        (0, 2),
        (0, 4),
        
        (1, 1),
        (1, 2),
        (1, 3),
        (1, 4),
        
        (2, 1),
        (2, 3),
        (2, 4),
        
        (3, 0),
        (3, 1),
        (3, 2),
        (3, 3),
    ];
    assert_eq!(calculate_max_complement(&arr), 27);
}

Ссылка на playground: https://play.rust-lang.org/?gist=77d643969db1caddabd410ee4a0ed392&version=stable