Определить, является ли один треугольник поворотом другого

Question

Вопрос относится к этой задаче ACMP: Ссылка

По координатам точек треугольников А и Б нужно определить, можно ли получить А из Б с помощью поворота. Я сравнивал треугольники "в лоб" и считал ориентированную (пусть и двойную) площадь, но это не дало нужного результата:

int sgn_area(int x1, int y1, int x2, int y2, int x3, int y3) {
    return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}

bool triangle_equal(float a1, float b1, float c1, float a2, float b2, float c2)
{
    if (a1 == a2 && b1 == b2 && c1 == c2 ||
        a1 == b2 && b1 == c2 && c1 == a2 ||
        a1 == c2 && b1 == a2 && c1 == b2 ||
        a1 == a2 && b1 == c2 && c1 == b2 ||
        a1 == c2 && b1 == b2 && c1 == a2 ||
        a1 == b2 && b1 == a2 && c1 == c2)
        return true;
    return false;
}

Некоторые наборы входных данных:

2
8 4 9 5 6 5
9 8 8 9 6 8
NO
-----------
2
4 1 5 4 4 5
2 8 2 12 1 11
NO
-----------
2
1 2 3 4 3 3
1 2 3 4 2 4
NO
-----------
2
1 1 4 1 2 2
1 1 4 1 3 2
NO
-----------
3
1 1 1 2 2 1
2 1 2 2 1 2
1 1 2 1 2 2
YES
-----------
2
0 0 0 1 2 0
3 0 5 0 3 1
YES

Answer 1

Вероятно, дело в порядке сторон. Две треугольника, полученные один из другого осевой симметрией, проходят Вашу проверку равенства сторон, но не являются поворотами друг друга.

Answer 2

Во-первых, не надо никаких float - их, по большому счету, нельзя сравнивать на равенство.

Собираем целочисленные квадраты сторон и сравниваем. Проще - отсортировав.

Чтобы проверить, не зеркальное ли отображение - да, берем векторное произведение. Но! двух соответствующих сторон - скажем, наименьших - и в одном порядке. Без особых изысков - вот:

int sq(int x) { return x*x; }

int prod(int x, int y, int x0, int y0, int x1, int y1)
{
    if (sq(x0-x)+sq(y0-y) > sq(x1-x)+sq(y1-y))
    {
        int t = x0; x0 = x1; x1 = t;
        t = y0; y0 = y1; y1 = t;
    }
    return (x0-x)*(y1-y)-(x1-x)*(y0-y);
}

vector<int> getTri()
{
    int x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    vector<int> t;
    int a, b, c;
    t.push_back(a = sq(x1-x2)+sq(y1-y2));
    t.push_back(b = sq(x2-x3)+sq(y2-y3));
    t.push_back(c = sq(x3-x1)+sq(y3-y1));
    sort(t.begin(),t.end());
    if (t[0] == t[1]) t.push_back(0);
    else
    {
        if (t[2] == a) t.push_back(prod(x3,y3,x2,y2,x1,y1));
        if (t[2] == b) t.push_back(prod(x1,y1,x2,y2,x3,y3));
        if (t[2] == c) t.push_back(prod(x2,y2,x3,y3,x1,y1));
    }
    return t;
}

int main(int argc, char * argv[])
{
    int N;
    cin >> N;
    vector<vector<int>> ts;
    for(int i = 0; i < N; ++i)
    {
        ts.push_back(getTri());
    }
    for(int i = 1; i < N; ++i)
    {
        if (ts[i] != ts[0]) { cout << "NO\n"; return 0; }
    }

    cout << "YES\n";
}

БЛОГ НА HUSL

Определить, является ли один треугольник поворотом другого

Ответы (2 шт):