package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	//"slices"
	"strconv"
	"strings"
)

var red_walls [][]int
var lines map[int][][]int
var columns map[int][][]int
var the_map map[[2]int]byte
var max_x,min_x int
var max_y,min_y int

func main() {
	fmt.Println("Advent of Code 2025 - Day 9 - Part 2")
	f,_:= os.Open("9/input")
	defer f.Close()
	scanner:=bufio.NewScanner(f)
	max_x = 0
	min_x = math.MaxInt
	max_y = 0
	min_y = math.MaxInt
	the_map = make(map[[2]int]byte)
	for scanner.Scan(){
		line:= scanner.Text()
		line_sp := strings.Split(line, ",")
		x,_:= strconv.Atoi(line_sp[0])
		y,_:= strconv.Atoi(line_sp[1])
		max_x = max(x,max_x)
		min_x = min(x,min_x)
		max_y = max(y,max_y)
		min_y = min(y,min_y)
		red_walls = append(red_walls, []int{x,y})
		the_map[[2]int{x,y}] = '#'
	}
	construct_border()
	//fmt.Println(len(lines))
	//fmt.Println(len(columns))
	construct_map()
	print_map()
	res := int64(0)
	for i:= range red_walls {
		w1:= red_walls[i]
		for j:= i+1; j < len(red_walls); j++{
		w2:= red_walls[j]
			if (is_valid_area(w1,w2)){
				area := calculate_area2(w1,w2)
				if area > res {
					//				fmt.Println(w1,w2)
					res = area
				}
			}
		}
	}
	fmt.Println(res)
}

func construct_map(){
 	for i:= min_x; i <= max_x; i++ {
 		for j:= min_y; j <= max_y; j++{
 			if the_map[[2]int{i,j}] != '#'{
				if is_green_or_red([]int{i,j}) {
					the_map[[2]int{i,j}] = 'O'
				} else {
					the_map[[2]int{i,j}] = '.'
				}
 			}
 		} 
 	}
}

func print_map(){
	for i := range 15 {
		for j:= range 15{
			c,ok := the_map[[2]int{j,i}]
			if ok {
				fmt.Printf(string(c))
			} else {
				fmt.Printf(".")
			}
		}
		fmt.Printf("\n")
	}
}



func construct_border() {
	lines = make(map[int][][]int)
	columns = make(map[int][][]int)
	for i:= 0; i < len(red_walls); i++{
		px,py := red_walls[(i+1)%len(red_walls)][0], red_walls[(i+1)%len(red_walls)][1]
		x,y:= red_walls[i][0], red_walls[i][1]
		
		if x == px {
			// lines from min(y,py) to max(y,py)
			for ln := min(y, py); ln <= max(y, py); ln++ {
				new_l := true
				_,ok := lines[ln]
				if ok{
					for i:= range lines[ln] {
						if lines[ln][i][0] <= x && x <= lines[ln][i][1] {
							lines[ln][i][0] = min(lines[ln][i][0], x)
							lines[ln][i][1] = max(lines[ln][i][1], x)
							new_l = false
							break
						}
					}
				}
				if new_l{
					lines[ln] = append(lines[ln], []int{x,x})
				}
			}
			// column x
			new_c := true
			a,b := min(y,py), max(y,py)
			_,ok := columns[x]
			if ok{
				for i:= range columns[x] {
					if columns[x][i][0] <= a && a <= columns[x][i][1] {
						columns[x][i][0] = min(columns[x][i][0], a)
						columns[x][i][1] = max(columns[x][i][1], b)
						new_c = false
						break
					}
				}
			}
			if new_c{
				columns[x] = append(columns[x], []int{a,b})
			}
		} else if y == py {
			// line y
			new_l := true
			a,b := min(x,px), max(x,px)
			_,ok := lines[y]
			if ok{
				for i:= range lines[y] {
					if lines[y][i][0] <= a && a <= lines[y][i][1] {
						lines[y][i][0] = min(lines[y][i][0], a)
						lines[y][i][1] = max(lines[y][i][1], b)
						new_l = false
						break
					}
				}
			}
			if new_l{
				lines[y] = append(lines[y], []int{min(x,px),max(x,px)})
			}
			// columns from min(x,px) to max(x,px)
			for cn := min(x, px); cn <= max(x, px); cn++ {
				new_c := true
				_,ok := columns[cn]
				if ok{
					for i:= range columns[cn] {
						if columns[cn][i][0] <= y && y <= columns[cn][i][1] {
							columns[cn][i][0] = min(columns[cn][i][0], y)
							columns[cn][i][1] = max(columns[cn][i][1], y)
							new_c = false
							break
						}
					}
				}
				if new_c{
					columns[cn] = append(columns[cn], []int{y,y})
				}
			}
		}
	}
}

// Given a point []int{x,y} look for the border to the 4 directions (W,N,E,S)
// B_W should have same y and <= x
// B_E should have same y and >= x
// B_N should have same x and >= y
// B_S should have same x and <= y
// if all borders are found then the point is a green or red wall
// otherwise it's out of boundaries
func is_green_or_red(w []int) bool {
	if is_border(w) {
		return true
	}
	ok_bw,ok_be := false,false
	ok_bn,ok_bs := false,false
	x,y := w[0],w[1]
	_,ok:= lines[y]
	if !ok {
		return false
	}
	_,ok = columns[x]
	if !ok {
		return false
	}
	
	// look for bordeer B_w & B_E
	for i:= range lines[y] {
		if ok_bw && ok_be{
			break
		}
		if !ok_bw && (lines[y][i][0] <= x || lines[y][i][1] <= x) {
			ok_bw = true
		}
		if !ok_be && (lines[y][i][0] >= x || lines[y][i][1] >= x) {
			ok_be = true
		}
	}
	if !ok_bw || !ok_be{
		return false
	}

	// look for bordeer B_N & B_S
	for i:= range columns[x] {
		if ok_bn && ok_bs{
			break
		}
		if !ok_bn && (columns[x][i][0] >= y || columns[x][i][1] >= y) {
			ok_bn = true
		}
		if !ok_bs && (columns[x][i][0] <= y || columns[x][i][1] <= y) {
			ok_bs = true
		}
	}
	if !ok_bw || !ok_be{
		return false
	}

	return ok_be && ok_bw && ok_bn && ok_bs
} 

func is_valid_area(w1,w2 []int) bool{
	x1,y1:=w1[0],w1[1]
	x2,y2:=w2[0],w2[1]

	start_x, end_x := min(x1,x2), max(x1,x2) // 2,11
	start_y, end_y := min(y1,y2), max(y1,y2) // 1,5
	for i:= start_x+1; i < end_x; i++{
		if (the_map[[2]int{i,y1}] == '.'){
			return false
		}
		if (the_map[[2]int{i,y2}] == '.'){
			return false
		}
	}
	for i:= start_y+1; i < end_y; i++{
		if (the_map[[2]int{x2,i}]== '.'){
				return false
		}
		if (the_map[[2]int{x1,i}] == '.'){
			return false
		}
	}
	return true
}


func is_border(w []int) bool {
	borders, ok := lines[w[1]]
	if ok {
		for i:= range borders{
			if borders[i][0] <= w[0] && w[0] <= borders[i][1]{
				return true
			}
		}
	}
	return false
}

func calculate_area2(w1,w2 []int) int64{
	dx, dy := int64(math.Abs(float64(w1[0]-w2[0]))), int64(math.Abs(float64(w1[1]-w2[1])))
	return (dx+1) * (dy+1)
}