from dataclasses import dataclass
from copy import copy, deepcopy
import math
from bisect import bisect_left

@dataclass
class Point:
    row: int
    col: int

    def neighbours4(self):
        return [Point(self.row+x, self.col+y) for x, y in [(0, 1), (0, -1), (-1,0), (1, 0)]]

    def __hash__(self) -> int:
        return ( self.row << 8 ) + self.col

    def __sub__(self, other):
        return Point(self.row-other.row, self.col-other.col)

class Map:
    def __init__(self, vertices: list[Point]) -> None:
        def normalize_points(points: list[Point]) -> list[Point]:
            min_row = min(points, key=lambda p: p.row).row
            min_col = min(points, key=lambda p: p.col).col
            return [Point(point.row-min_row, point.col-min_col) for point in points]

        vertices_normalized = normalize_points(vertices)

        def create_bins(points: list[Point], for_rows: bool) -> list[int]:
            unique = sorted(list(set([ p.row if for_rows else p.col for p in points])))
            bins = []
            for p in unique:
                bins.append(p)
                bins.append(p+1)
            return bins

        self.row_bins = create_bins(vertices_normalized, True)
        self.col_bins = create_bins(vertices_normalized, False)

        self.row_count = len(self.row_bins)-1
        self.col_count = len(self.col_bins)-1
        vertices_compressed = []
        for p in vertices_normalized:
            cp = self.to_compressed(p)
            vertices_compressed.append(cp)

        vertices_compressed.append(copy(vertices_compressed[0]))

        # Create loop points by vertices.
        def create_points(vertices: list[Point]) -> list[Point]:
            prev = vertices[0]
            points = [prev]
            for i in range(1, len(vertices)):
                curr = vertices[i]

                if curr.row == prev.row:
                    if prev.col < curr.col:
                        for col in range(prev.col, curr.col):
                            points.append(Point(curr.row, col))
                    else:
                        for col in range(curr.col+1, prev.col+1):
                            points.append(Point(curr.row, col))
                else:
                    assert curr.col == prev.col
                    if prev.row < curr.row:
                        for row in range(prev.row, curr.row):
                            points.append(Point(row, curr.col))
                    else:
                        for row in range(curr.row+1, prev.row+1):
                            points.append(Point(row, curr.col))

                prev = curr
            return points

        self.points = create_points(vertices_compressed)

        self.data = [['.' for c in range(self.col_count)] for r in range(self.row_count)]
        all_points = set(self.points)
        for p in self.iterate_points():
            if p in all_points:
                self.data[p.row][p.col] = '#'
        self.digged = deepcopy(self.data)


    def to_compressed(self, p: Point):
        r = bisect_left(self.row_bins, p.row)
        c = bisect_left(self.col_bins, p.col)
        return Point(r, c)


    def compressed_weight(self, p: Point):
        return (self.row_bins[p.row+1] - self.row_bins[p.row])*(self.col_bins[p.col+1]-self.col_bins[p.col])


    def dig_point(self, p: Point):
        self.data[p.row][p.col] = '#'

    def iterate_points(self):
        for row in range(self.row_count):
            for col in range(self.col_count):
                yield Point(row, col)


    # Angle between vectors ap and bp
    def calc_angle(self, p: Point, a: Point, b: Point):
        _a = a - p
        _b = b - p
        dy = _a.col * _b.row - _a.row * _b.col
        dx = _a.col * _b.col + _a.row * _b.row
        return math.atan2(dy, dx)


    # Tests if the point is inside the polygon
    def inside(self, p: Point):
        total = 0
        prev = copy(self.points[0])
        for i in range(1, len(self.points)):
            cur = copy(self.points[i])
            total += self.calc_angle(p, prev, cur)
            prev = copy(cur)
        return abs(total) > 0.5


    def dig_nearby(self, start: Point, value: str):
        front = [start]
        while len(front) > 0:
            new_front = []
            for p in front:
                if 0 <= p.row < self.row_count and 0 <= p.col < self.col_count:
                    if self.digged[p.row][p.col] == '.':
                        self.digged[p.row][p.col] = value
                        new_front += p.neighbours4()
            front = new_front


    def dig_inside(self):
        for p in self.iterate_points():
            if self.digged[p.row][p.col] == '.':
                if self.inside(p):
                    self.dig_nearby(p, '#')
                else:
                    self.dig_nearby(p, '_')


    def calc_digged(self):
        total = 0
        for p in self.iterate_points():
            if self.digged[p.row][p.col] == '#':
                total += self.compressed_weight(p)
        return total


class Command:
    DIRECTION_MAP = {0: 'R', 1: 'D', 2: 'L', 3: 'U'}

    def __init__(self, line: str) -> None:
        parts = line.strip().replace('(','').replace(')', '').replace('#', '').split(' ')
        color = parts[2]
        self.steps = int(color[0:5],16)
        self.direction = Command.DIRECTION_MAP[int(color[-1])]


class Input:
    def __init__(self, path: str) -> None:

        with open(path, 'r') as file:
            lines = file.readlines()
            self.commands = [Command(line) for line in lines]

    def process(self):
        nodes: list[Point] = []
        point = Point(0, 0)

        for command in self.commands:
            if command.direction == 'U':
                point.row -= command.steps
            elif command.direction == 'D':
                point.row += command.steps
            elif command.direction == 'L':
                point.col -= command.steps
            elif command.direction == 'R':
                point.col += command.steps
            nodes.append(copy(point))
        return Map(nodes)


input = Input('day18.txt')
map = input.process()
map.dig_inside()

print(map.calc_digged())