9

Решаю задачу из Тинькофф.Контест. Условие следующее:

Миша сидел в переговорке и решил нарисовать ее план на листке бумаги. Когда он закончил рисовать план переговорки, он положил лист с планом на пол переговорки. Теперь ему стало интересно: а есть ли на плане точка, которая лежит ровно на том месте пола, за которое она отвечает? Помогите ему найти эту точку.

Формат входных данных:

Переговорка и ее план имеют форму прямоугольника. Первая строка входного файла содержит два вещественных числа: координаты X и Y переговорки. Координаты углов переговорки равны (0,0),(X,0),(X,Y),(0,Y).
Вторая строка - восемь вещественных чисел, описывающих положение углов плана переговорки.

Пример данных:

Ввод:

10 5

3.0 2.5 1.0 2.5 1.0 1.5 3.0 1.5

Вывод: 2.5000 2.0833

Я решил задачу для случаев, когда ось X плана переговорки параллельна оси Y или X самой переговорки. Т.е в этих случаях:

введите сюда описание изображения

Вот мой код:

public static (double x, double y) Task8(double x, double y, double[] corners)
        {
            // заношу координаты планерки в массив, чтоб было удобнее обращаться к углам
            // [0, 0] = (0, 0), [1, 0] = (x, 0), [0, 1] = (0, y), [1, 1] = (x, y)
            (double x, double y)[,] planCornersCoordinates = new (double x, double y)[2, 2];
            planCornersCoordinates[0, 0] = (corners[0], corners[1]);
            planCornersCoordinates[1, 0] = (corners[2], corners[3]);
            planCornersCoordinates[1, 1] = (corners[4], corners[5]);
            planCornersCoordinates[0, 1] = (corners[6], corners[7]);

            // Вычисляю масштаб
            double planXLenght = Math.Abs(planCornersCoordinates[0, 0].x - planCornersCoordinates[1, 1].x);
            double planYLenght = Math.Abs(planCornersCoordinates[0, 0].y - planCornersCoordinates[1, 1].y);
            double planSquare = planXLenght * planYLenght;
            double square = x * y;
            double scale = Math.Sqrt(square / planSquare);

            // Если ось X плана планерки параллельна оси X самой планерки, то просто решаю два уравнения с одной переменной
            if (planCornersCoordinates[0, 0].y == planCornersCoordinates[1, 0].y)
            {
                var signX = -Math.Sign(planCornersCoordinates[1, 0].x - planCornersCoordinates[0, 0].x);
                var signY = -Math.Sign(planCornersCoordinates[0, 1].y - planCornersCoordinates[0, 0].y);
                x = (planCornersCoordinates[0, 0].x * scale) / (scale + signX);
                y = (planCornersCoordinates[0, 0].y * scale) / (scale + signY);
            }

            // Если ось X плана планерки параллельна оси Y самой планерки, то решаю систему из двух уравнений
            // с двумя переменными методом Крамера
            if (planCornersCoordinates[0, 0].x == planCornersCoordinates[1, 0].x)
            {
                var signX = Math.Sign(planCornersCoordinates[1, 0].y - planCornersCoordinates[0, 0].y);
                var signY = Math.Sign(planCornersCoordinates[0, 1].x - planCornersCoordinates[0, 0].x);
                var determinant = 1 / scale * signX * signY * 1 / scale - 1;
                var determinantX = -planCornersCoordinates[0, 0].y * 1 / scale * signY - planCornersCoordinates[0, 0].x;
                x = determinantX / determinant;
                var determinantY = -planCornersCoordinates[0, 0].x * 1 / scale * signX - planCornersCoordinates[0, 1].y;
                y = determinantY / determinant;
            }
            return (x, y);
        }

Но я не могу решить задачу, когда план повернут на какой-нибудь угол. Примерно такая ситуация:

введите сюда описание изображения

Я пытаюсь составить уравнение с использованием косинуса этого угла, но так и не понял, как это нужно сделать.

Я создал репозиторий с полным условием задачи, кодом и юнит-тестами: https://github.com/ByMyKolaps/Task8_Tinkoff

5
  • Что такое положение углов плана переговорки?
    – tym32167
    13 мар в 22:21
  • Координаты вершин плана, @tym32167 14 мар в 5:04
  • 1
    Ну в голову приходит наивное решение: искомая точка точно находится там, где в переговорке лежит план, значит надо на плане нарисовать положение плана. Далее выполняем этот алгоритм рекурсивно пока не достигнем требуемой точности. Т.к масштаб плана строго меньше 1, то на каждом шаге размеры будут гарантировано уменьшаться. Проблема: в худшем случае может потребоваться очень много итераций 14 мар в 5:14
  • 1
    Хочется решить как-то более математически на самом деле, взять любую точку плана, например, левый нижний угол и исследовать как координаты этой точки меняются в алгоритме выше, т.е. будет некий ряд, надо найти точку сходимости ряда, она и будет ответом 14 мар в 5:21
  • 2
    Просто надо очень аккуратно расписать матрицу аффинного преобразования. В принципе, ее можно вычислить из соответствия точек углов прямоугольников. Просто сесть и расписать требует достаточно большого времени, которого вечно не хватает... так что уж попробуйте самостоятельно, как в учебниках пишут — "в качестве самостоятельной работы"... :)
    – Harry
    14 мар в 5:46

3 ответа 3

10

Если сжатие пропорционально и порядок углов плана соответствует порядку 00-X0-XY-0Y, то можно вычислить

scale = len(edge1) / X
rot = atan2(y1-y0, x1-x0)
shift = x0, y0

и составить матрицу аффинного преобразования M как произведение трех матриц выше (в таком порядке)

        sc 0  0    
mscl =  0  sc 0
        0  0  1

       cos(rot) -sin(rot)  0    
mrot = sin(rot)  cos(rot)  0
       0         0         1

         1   0   0    
mshft =  0   1   0
         x0  y0  1

Затем решить систему уравнений

(tx, ty, 1) * [M] = (tx, ty, 1)
3
  • Из последней системы M = Id? 14 мар в 6:44
  • 2
    @Андрей NOP Нужно найти tx, ty - собственный вектор матрицы
    – MBo
    14 мар в 6:46
  • Помимо сжатия и поворота может быть ещё отражение - листок перевернулся, и ориентация обхода вершин изменилась. Первые несколько тесткейсов именно такие.
    – Pak Uula
    15 мар в 1:56
9

Как решить без матриц.

Пусть в системе координат сторон прямоугольника координаты некоторой точки (a,b) - то есть по оси Ox координата точки a*AB, а по оси Oy - b*AD. Тогда у точки, в которую переходит данна, координаты внутри прямоугольника будут тоже (a,b): x' = A'_x + a*A'B', y' = A'_y + b*A'D'

введите сюда описание изображения

Для поиска неподвижной точки достаточно приравнять x==x' && y==y'. Система уравнений относительно a и b на рисунке выше.

Прошу простить, в C# плаваю, писал последний раз лет 10 назад, поэтому я вам дам решение на Пайтоне, хорошо?

Для начала класс Матрица-два-на-два, чтобы решать по формуле Крамера

class Matrix2x2:
    def __init__(self, rows) -> None:
        self.rows = rows
    def det(self):
        "Детерминант"
        return self[0,0]*self[1,1]-self[0,1]*self[1,0]
    def __getitem__(self, idx):
        "Функция индексации: позволяет писать `m[0,1]` для коэффициента в первой строке и втором столбце."
        if isinstance(idx, tuple):
            return self.rows[idx[0]][idx[1]]
        raise ValueError("Not a tuple: ", idx)
    def replace_col(self, col, a1, a2):
        "Меняет колонку с номером col на столбец [a1, a2] (транспонированный)"
        if col == 0:
            return Matrix2x2([[a1, self[0,1]],[a2, self[1,1]]])
        elif col == 1:
            return Matrix2x2([[self[0,0], a1],[self[1,0], a2]])
        else:
            raise ValueError("Out of bounds: ", col)
    def solve_eq(self, x, y):
        "Решает систему линейных уравнений с правой частью [x, y]"
        d0 = self.det()
        m1 = self.replace_col(0, x,y)
        m2 = self.replace_col(1, x,y)
        return m1.det()/d0, m2.det()/d0
        
    def __repr__(self):
        "ToString"
        return f"{self.rows}"

Теперь решатель и ваши тестовые случаи:

tests = [
        [(10, 5), ( 4.5, 2.0, 4.5, 4.0, 5.5, 4.0, 5.5, 2.0 ), (5.104166, 3.020833)],
        [(10, 5), ( 4.5, 4.0, 4.5, 2.0, 5.5, 2.0, 5.5, 4.0 ), (5.09615, 2.98076)],
        [(10, 5), ( 5.5, 4.0, 5.5, 2.0, 4.5, 2.0, 4.5, 4.0 ), (4.89583, 3.020833)],
        [(10, 5), ( 5.5, 2.0, 5.5, 4.0, 4.5, 4.0, 4.5, 2.0 ), (4.90384, 2.98076)],

        [(10, 5), ( 1.0, 1.5, 3.0, 1.5, 3.0, 2.5, 1.0, 2.5 ), (1.25, 1.875)],
        [(10, 5), ( 3.0, 1.5, 1.0, 1.5, 1.0, 2.5, 3.0, 2.5 ), (2.5, 1.875)],
        [(10, 5), ( 3.0, 2.5, 1.0, 2.5, 1.0, 1.5, 3.0, 1.5 ), (2.5, 12.5 / 6)],
        [(10, 5), ( 1.0, 2.5, 3.0, 2.5, 3.0, 1.5, 1.0, 1.5 ), (1.25, 12.5 / 6)]    
]

def solve(test_case):
    (A,D),(Ax,Ay,Bx,By,_,_,Dx,Dy),_ = test_case
    m = Matrix2x2([
        [A-Bx+Ax, -Dx+Ax],
        [-By+Ay, D-Dy+Ay]
    ])
    x,y = m.solve_eq(Ax,Ay)
    return x*A, y*D

def test(test_case):
    print(solve(test_case),test_case[-1])

for tc in tests:
    test(tc)

Результат. В каждой строке первая пара - найденное решение, вторая пара ожидаемое значение.

(5.104166666666666, 3.020833333333333) (5.104166, 3.020833)
(5.096153846153846, 2.980769230769231) (5.09615, 2.98076)
(4.895833333333333, 3.020833333333333) (4.89583, 3.020833)
(4.903846153846153, 2.980769230769231) (4.90384, 2.98076)
(1.25, 1.875) (1.25, 1.875)
(2.5, 1.875) (2.5, 1.875)
(2.5, 2.0833333333333335) (2.5, 2.0833333333333335)
(1.25, 2.0833333333333335) (1.25, 2.0833333333333335)
4

Вот решение вашей задачи:

    public static (double x, double y) Task8(double x, double y, double[] corners) {
        double xx = 0;
        double yy = 0;
        for (int i = 0; i < 100; ++i) {
            double alpha = xx / x;
            double beta = yy / y;

            xx = (1 - alpha) * ((1 - beta) * corners[0] + beta * corners[6]) + 
                      alpha  * ((1 - beta) * corners[2] + beta * corners[4]);
            yy = (1 - alpha) * ((1 - beta) * corners[1] + beta * corners[7]) + 
                      alpha  * ((1 - beta) * corners[3] + beta * corners[5]);
        }
        return (xx, yy);
    }

(xx, yy) - точка на полу комнаты. В цикле вычисляются координаты точки относительно углов точки: (alpha, beta). Имея координаты углов плана можно вычислить где точка (alpha, beta) на плане окажется в комнате. Эта процедура повторяется сто раз и получается ответ.

Отображение которое переводит точку в комнате в точку на плане и снова в точку в комнате - сжимающее. Это значит что если вы возьмёте две любые точки в комнате, отобразите их, расстояние между образами будет меньше чем расстояние между исходными точками. Это очевидно - план всё-таки куда меньше комнаты. Из математического анализа известно что сжимающее отображение имеет предельную точку и она единственная. Вы можете выбрать любую начальную точку, преобразовывать её раз за разом и, после бесконечного количества преобразований точка окажется в пределе. У меня число повторений не бесконечное, но достаточное. Я прикинул что план всяко не больше половины комнаты. Это значит после каждого отображения точка оказывается в два раза ближе к пределу. В начале цикла точка в комнате, то есть, скажем на расстоянии x от предела. В конце цикла точка окажется на расстоянии x / 2^100 от предела. Это меньше точности double, которая равна x / 2^53. Понятно, что если лист по размеру близок к комнате или даже больше комнаты, метод не работает.

Более правильно делать не фиксированное число итераций, а продолжать отображать точку пока не достигнута нужная точность. Оставлю это в качестве упражнения.

Метод называется "решение системы линейных уравнений методом простых итераций".

То что задача имеет такое "дешёвое" решение не означает что вам не нужно знать что такое математический анализ и линейная алгебра. Это решение не во всех ситуациях применимо, в отличие от других ответов.

5
  • А почему всегда 50 итераций? А если масштаб 0.9999999999? 14 мар в 21:06
  • Если масштаб очень близок к единице весь метод не работает. Всё потонет в шуме от ошибок округления. 14 мар в 21:07
  • Ну по условию задачи масштаб <1, значит может быть и таким, и я бы на месте составителей предусмотрел тесткейс такой 14 мар в 21:11
  • @АндрейNOP, только что прочитал ваши комментарии. Теперь чувствую себя неловко. Вот чтобы вам не оформить их в виде ответа? 14 мар в 21:14
  • Ну такие ответы уже есть, лучше мне не написать :) ваш ответ тоже должен остаться, но с комментариями, чтобы было понятно какие могут быть недостатки 14 мар в 21:16

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.