Monikulmio

use std::io;
use std::cmp;
use std::collections::HashMap;
use std::ops::Range;

fn main() {
    let mut input: String = String::new();
    io::stdin().read_line(&mut input).unwrap();
    
    let input: Vec<i32> = input.trim().split(" ").map(|s| s.parse::<i32>().unwrap()).collect();

    let points: Vec<(i32, i32)> = get_points(input[2]);
    let points_order: HashMap<(i32, i32), usize> = get_points_order(&points);

    let mut polygon: Vec<String> = draw_grid(input[0], input[1], &points);
    polygon = draw_outlines(polygon, &points);
    polygon = fill_polygon(polygon, &points, &points_order);
    
    print_result(&polygon);
}

fn get_points(k: i32) -> Vec<(i32, i32)> {
    let mut points: Vec<(i32, i32)> = Vec::new();
    for _ in 0 .. k {
        let mut point: String = String::new();
        io::stdin().read_line(&mut point).unwrap();
        let parsed: Vec<i32> = point.trim().split(" ").map(|s| s.parse::<i32>().unwrap()).collect();
        points.push((parsed[0]-1, parsed[1]-1));
    }
    return points;
}

fn get_points_order(points: &Vec<(i32, i32)>) -> HashMap<(i32, i32), usize> {
    let mut points_order: HashMap<(i32, i32), usize> = HashMap::new();
    for i in 0..points.len() {
        points_order.insert(points[i], i);
    }
    return points_order;
}

fn draw_grid(n: i32, m: i32, points: &Vec<(i32, i32)>) -> Vec<String> {
    let mut polygon: Vec<String> = Vec::new();

    for y in 0 .. n {
        let mut row: String = String::new();
        for x in  0.. m {
            let char: char = if !points.contains(&(y, x)) { '.' } else { '*' };
            row.push(char);
        };
        polygon.push(row);
    }

    return polygon;
}

fn draw_outlines(mut polygon: Vec<String>, points: &Vec<(i32, i32)>) -> Vec<String> {
    for i in 0 .. points.len() {
        let p1: (i32, i32) = points[i];
        let p2: (i32, i32) = points[(i + 1) % points.len()];

        let dy: i32 = p2.0 - p1.0;
        let dx: i32 = p2.1 - p1.1;
        let c: char = if dx == 0 { '|' } else if dy == 0 { '=' } else if (dx < 0 && dy < 0) || (dx > 0 && dy > 0) { 92 as char } else { '/' };
        
        for j in 0 .. (cmp::max(dx.abs(), dy.abs())-1) {
            let y: i32 = p1.0 + dy.clamp(-1, 1) * (j + 1);
            let x: i32 = p1.1 + dx.clamp(-1, 1) * (j + 1);
            polygon[y as usize].replace_range(x as usize..(x + 1) as usize, c.to_string().as_str());
        }
    }

    return polygon;
}

fn fill_polygon(mut polygon: Vec<String>, points: &Vec<(i32, i32)>, points_order: &HashMap<(i32, i32), usize>) -> Vec<String> {
    for i in 0 .. polygon.len() {
        let copy: Vec<String> = polygon.clone();
        let indicies: Vec<_>  = copy[i].match_indices(&['|', '=', '/', 92 as char, '*'][..]).collect();
        if indicies.len() > 0 {
            for j in 0 .. indicies.len() - 1 {
                let c1: (usize, &str) = indicies[j];
                let c2: (usize, &str) = indicies[j + 1];
                if c2.0 - c1.0 > 1 && is_valid_fill(&polygon, c1, i, points, points_order) {
                    polygon[i].replace_range(c1.0 +  1 .. c2.0, "#".repeat(c2.0 - c1.0 - 1).as_str());
                }
            }
        }
    }
    
    return polygon;
}

fn is_valid_fill(polygon: &Vec<String>, c1: (usize, &str), row: usize, points: &Vec<(i32, i32)>, points_order: &HashMap<(i32, i32), usize>) -> bool {
    let ray_origin: usize = c1.0 + 1;
    let direction: i8 = if ray_origin < polygon[0].len() / 2 { -1 } else { 1 };

    let ray: String = polygon[row].clone();
    let top_row: String = if row > 0 { polygon[row - 1].clone() } else { String::new() };
    let bottom_row: String = if row < polygon.len() - 1 { polygon[row + 1].clone() } else { String::new() };

    let ray_range: Range<usize> = if direction < 0 { 0..ray_origin } else { ray_origin..ray.len() };
    let mut in_wall: bool = false;
    let mut above_needed: bool = false;

    let mut intersections: usize = 0;
    let hits: Vec<_> = ray.match_indices(&['|', '/', 92 as char, '*'][..]).collect();
    for hit in hits {
        if !ray_range.contains(&hit.0) { continue; }
        if ray.as_bytes()[hit.0] as char != '*' { intersections += 1; continue; }

        let p1: (i32, i32) = (row as i32, hit.0 as i32);
        let surrounding: HashMap<String, bool> = get_surrounding(p1, &top_row, &bottom_row, polygon.len(), points_order);

        if hit.0 + 2 < ray.len() {
            let next: char = ray.as_bytes()[hit.0 + 1] as char;

            if !in_wall {
                if next == '=' || (next == '*' && check_sequence_point(p1, (p1.0, p1.1 + 1), points_order)) {
                    in_wall = true;
                    above_needed = check_direction_needed(p1, points, points_order);
                    intersections += 2;
                } else {
                    intersections += check_double(&surrounding);
                }
            } else {
                let wall_check: i32 = check_wall_end(p1, above_needed, &surrounding, points, points_order);
                if wall_check > -1 {
                    in_wall = false;
                    intersections += wall_check as usize;
                }
            }
        } else {
            if !in_wall {
                intersections += check_double(&surrounding);
            } else {
                let wall_check: i32 = check_wall_end(p1, above_needed, &surrounding, points, points_order);
                if wall_check > -1 {
                    intersections += wall_check as usize;
                }
            }
        }
    }

    return intersections % 2 == 1;
}

fn get_surrounding(p1: (i32, i32), top_row: &String, bottom_row: &String, row_count: usize, points_order: &HashMap<(i32, i32), usize>) -> HashMap<String, bool> {
    let mut surrounding: HashMap<String, bool> = HashMap::new();

    surrounding.insert("tl".to_string(), check_sequence(top_row, p1, -1, -1, row_count, points_order));
    surrounding.insert("tm".to_string(), check_sequence(top_row, p1, -1, 0, row_count, points_order));
    surrounding.insert("tr".to_string(), check_sequence(top_row, p1, -1, 1, row_count, points_order));

    surrounding.insert("bl".to_string(), check_sequence(bottom_row, p1, 1, -1, row_count, points_order));
    surrounding.insert("bm".to_string(), check_sequence(bottom_row, p1, 1, 0, row_count, points_order));
    surrounding.insert("br".to_string(), check_sequence(bottom_row, p1, 1, 1, row_count, points_order));
    
    return surrounding;
}

fn check_sequence_point(p1: (i32, i32), p2: (i32, i32), points_order: &HashMap<(i32, i32), usize>) -> bool {
    let order1: i32 = *points_order.get(&p1).unwrap() as i32;
    let order2: i32 = *points_order.get(&p2).unwrap() as i32;
    return (order2 - order1).abs() == 1;
}

fn check_sequence(row: &String, p1: (i32, i32), row_offset: i32, col_offset: i32, row_count: usize, points_order: &HashMap<(i32, i32), usize>) -> bool {
    if p1.0 + row_offset > 0 && p1.0 + row_offset + 1 < row_count as i32 && p1.1 + col_offset > 0 && p1.1 + col_offset + 1 < row.len() as i32 {
        let c: char = row.as_bytes()[(p1.1 + col_offset) as usize] as char;

        if c == '*' {
            return check_sequence_point(p1, (p1.0 + row_offset, p1.1 + col_offset), points_order);
        }

        if row_offset < 0 {
            return (col_offset < 0 && c == 92 as char) || (col_offset == 0 && c == '|') || (col_offset > 0 && c == '/');
        } else {
            return (col_offset < 0 && c == '/') || (col_offset == 0 && c == '|') || (col_offset > 0 && c == 92 as char);
        }
    }
    return false;
}

fn check_direction_needed(p1: (i32, i32), points: &Vec<(i32, i32)>, points_order: &HashMap<(i32, i32), usize>) -> bool {
    let mut order: usize = *points_order.get(&p1).unwrap();
    if order == 0 { order += points.len(); }

    let mut p2: (i32, i32) = points[(order - 1) % points.len()];
    if p1.0 == p2.0 { p2 = points[(order + 1) % points.len()]; }

    return p1.0 - p2.0 < 0;
}

fn check_double(surrounding: &HashMap<String, bool>) -> usize {
    if *surrounding.get(&"tl".to_string()).unwrap() && *surrounding.get(&"tm".to_string()).unwrap() { return 2; }
    else if *surrounding.get(&"tl".to_string()).unwrap() && *surrounding.get(&"tr".to_string()).unwrap() { return 2; }
    else if *surrounding.get(&"tm".to_string()).unwrap() && *surrounding.get(&"tr".to_string()).unwrap() { return 2; }
    else if *surrounding.get(&"bl".to_string()).unwrap() && *surrounding.get(&"bm".to_string()).unwrap() { return 2; }
    else if *surrounding.get(&"bl".to_string()).unwrap() && *surrounding.get(&"br".to_string()).unwrap() { return 2; }
    else if *surrounding.get(&"bm".to_string()).unwrap() && *surrounding.get(&"br".to_string()).unwrap() { return 2; }

    return 1;
}

fn check_wall_end(p1: (i32, i32), above_needed: bool, surrounding: &HashMap<String, bool>, points: &Vec<(i32, i32)>, points_order: &HashMap<(i32, i32), usize>) -> i32 {
    let tl: bool = *surrounding.get(&"tl".to_string()).unwrap();
    let tm: bool = *surrounding.get(&"tm".to_string()).unwrap();
    let tr: bool = *surrounding.get(&"tr".to_string()).unwrap();
    let bl: bool = *surrounding.get(&"bl".to_string()).unwrap();
    let bm: bool = *surrounding.get(&"bm".to_string()).unwrap();
    let br: bool = *surrounding.get(&"br".to_string()).unwrap();

    if tl || tm || tr || bl || bm || br {
        let above: bool = !check_direction_needed(p1, points, points_order);

        if (above && above_needed) || (!above && !above_needed) { return 1; }
        else { return 0; }
    }

    return -1;
}

fn print_result(polygon: &Vec<String>) {
    for row in polygon {
        println!("{}", row);
    }
}

Test 1 (public)

Verdict: ACCEPTED

Test 2 (public)

Verdict: ACCEPTED

Test 3 (public)

Verdict: ACCEPTED

Test 4 (public)

Verdict: ACCEPTED

Test 5 (public)

Verdict: ACCEPTED

Test 6 (public)

Verdict: ACCEPTED

Test 7 (public)

Verdict: ACCEPTED

Test 8 (public)

Verdict: ACCEPTED

Test 9 (public)

Verdict: ACCEPTED

Test 10 (public)

Verdict: ACCEPTED