---

"""
Задача:
Черепаха выполнила программу:
    Повтори 2 [Вперёд 14 Налево 270 Назад 12 Направо 90]
    Поднять хвост
    Вперёд 9 Направо 90 Назад 7 Налево 90
    Опустить хвост
    Повтори 2 [Вперёд 13 Направо 90 Вперёд 6 Направо 90]

Найти, сколько точек с целочисленными координатами лежат внутри
пересечения фигур, ограниченных линиями (включая точки на самих линиях).
"""

from fractions import Fraction as F

# ---------------------------------------------------------------------------
# 1. Черепаха: т.к. все повороты кратны 90°, направление всегда совпадает
#    с одной из осей — считаем точно, без ошибок округления float.
# ---------------------------------------------------------------------------

DIRS = {0: (F(1), F(0)), 90: (F(0), F(1)), 180: (F(-1), F(0)), 270: (F(0), F(-1))}

class Turtle:
    def __init__(self):
        self.x, self.y = F(0), F(0)
        self.heading = 0          # 0, 90, 180 или 270
        self.pen_down = True
        self.path = [(self.x, self.y)]   # точки текущей (нарисованной) ломаной

    def _dir(self):
        return DIRS[self.heading % 360]

    def forward(self, d):
        dx, dy = self._dir()
        self.x += dx * d
        self.y += dy * d
        if self.pen_down:
            self.path.append((self.x, self.y))

    def backward(self, d):
        self.forward(-d)

    def left(self, a):
        self.heading = (self.heading + a) % 360

    def right(self, a):
        self.heading = (self.heading - a) % 360

    def pen_up(self):
        self.pen_down = False

    def pen_down_(self):
        self.pen_down = True
        self.path = [(self.x, self.y)]   # начинаем новую фигуру


def run_program():
    t = Turtle()

    # --- Первая фигура ---
    for _ in range(2):
        t.forward(14)
        t.left(270)
        t.backward(12)
        t.right(90)
    shape1 = dedupe(t.path)

    # --- Переход без рисования ---
    t.pen_up()
    t.forward(9)
    t.right(90)
    t.backward(7)
    t.left(90)
    t.pen_down_()

    # --- Вторая фигура ---
    for _ in range(2):
        t.forward(13)
        t.right(90)
        t.forward(6)
        t.right(90)
    shape2 = dedupe(t.path)

    return shape1, shape2


def dedupe(points):
    """Убираем повторяющиеся подряд точки (замыкание контура)."""
    out = [points[0]]
    for p in points[1:]:
        if p != out[-1]:
            out.append(p)
    if out[0] == out[-1]:
        out.pop()
    return out


# ---------------------------------------------------------------------------
# 2. Пересечение двух выпуклых многоугольников: Sutherland–Hodgman clipping.
#    Работает для любых выпуклых фигур, не только для прямоугольников.
# ---------------------------------------------------------------------------

def clip_polygon(subject, clip):
    def inside(p, a, b):
        # знак векторного произведения — с какой стороны от ребра (a->b) лежит p
        return (b[0]-a[0])*(p[1]-a[1]) - (b[1]-a[1])*(p[0]-a[0]) >= 0

    def intersect(p1, p2, a, b):
        x1, y1 = p1; x2, y2 = p2
        x3, y3 = a;  x4, y4 = b
        d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
        if d == 0:
            return p2
        t_ = ((x1-x3)*(y3-y4) - (y1-y3)*(x3-x4)) / d
        return (x1 + t_*(x2-x1), y1 + t_*(y2-y1))

    output = subject
    n = len(clip)
    for i in range(n):
        a, b = clip[i], clip[(i+1) % n]
        input_list = output
        output = []
        if not input_list:
            break
        for j in range(len(input_list)):
            cur = input_list[j]
            prev = input_list[j-1]
            cur_in = inside(cur, a, b)
            prev_in = inside(prev, a, b)
            if cur_in:
                if not prev_in:
                    output.append(intersect(prev, cur, a, b))
                output.append(cur)
            elif prev_in:
                output.append(intersect(prev, cur, a, b))
    return output


def ensure_ccw(poly):
    area2 = sum(poly[i][0]*poly[(i+1) % len(poly)][1] - poly[(i+1) % len(poly)][0]*poly[i][1]
                for i in range(len(poly)))
    return poly if area2 > 0 else poly[::-1]


# ---------------------------------------------------------------------------
# 3. Подсчёт целых точек внутри многоугольника И на его границе.
# ---------------------------------------------------------------------------

def point_on_segment(p, a, b):
    cross = (b[0]-a[0])*(p[1]-a[1]) - (b[1]-a[1])*(p[0]-a[0])
    if cross != 0:
        return False
    return min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and \
           min(a[1], b[1]) <= p[1] <= max(a[1], b[1])


def point_in_polygon(p, poly):
    n = len(poly)
    for i in range(n):
        if point_on_segment(p, poly[i], poly[(i+1) % n]):
            return True  # на границе — считаем как "внутри пересечения"
    # ray casting для строго внутренних точек
    x, y = p
    inside = False
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        if (y1 > y) != (y2 > y):
            xinters = x1 + (y - y1) * (x2 - x1) / (y2 - y1)
            if x < xinters:
                inside = not inside
    return inside


def count_lattice_points(poly):
    xs = [p[0] for p in poly]
    ys = [p[1] for p in poly]
    xmin, xmax = int(min(xs)), int(max(xs))
    ymin, ymax = int(min(ys)), int(max(ys))
    total = 0
    pts = []
    for X in range(xmin, xmax+1):
        for Y in range(ymin, ymax+1):
            if point_in_polygon((F(X), F(Y)), poly):
                total += 1
                pts.append((X, Y))
    return total, pts


# ---------------------------------------------------------------------------
# Основной запуск
# ---------------------------------------------------------------------------

if __name__ == "__main__":
    shape1, shape2 = run_program()
    print("Фигура 1 (вершины):", shape1)
    print("Фигура 2 (вершины):", shape2)

    shape1 = ensure_ccw(shape1)
    shape2 = ensure_ccw(shape2)

    intersection = clip_polygon(shape1, shape2)
    print("\nПересечение (вершины):", intersection)

    if intersection:
        total, pts = count_lattice_points(intersection)
        print(f"\nЦелочисленных точек внутри пересечения (включая границу): {total}")
        print("Точки:", sorted(pts))
    else:
        print("Фигуры не пересекаются.")