e-olymp 12. Поврежденная картина

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

Входные данные

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

Выходные данные

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные	Выходные данные
1 1 6 1 4 0 4 5 6	4.000
0 0 6 0 2 0 5 0 5	2.397
2 0 5 0 0 0 6 0 5	4.172
0 0 5 0 2 0 6 0 1	2.058
0 0 10 0 2 0 6 0 1	0.000

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

struct t {
    double x, y;
    t() {
        x = 0;
        y = 0;
    }
    t(double x, double y) {
        this->x = x;
        this->y = y;
    }
    t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }
        
    t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

    bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

    bool operator!=(t &p) { return !(*this == p); }

    bool t_is_line_segment(t &t1, t &t2) {
        t t3 = *this;
        t a = t2 - t1;
        t b = t3 - t1;
        double sa = a.x * b.y - b.x * a.y;
        if (sa > 0.0) return false;
        if (sa < 0.0) return false;
        if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;
        if (a.length() < b.length()) return false;
        if (t1 == t3) return false;
        if (t2 == t3) return false;
        return true;
    }
    double distance(const t &p) {
        double a = this->x - p.x;
        double b = this->y - p.y;
        return sqrt(a * a + b * b);
    }

    double length(void) { return sqrt(x * x + y * y); }
};

struct line {
    double a, b, c;
    line(const t &t1, const t &t2) {
    a = t1.y - t2.y;
    b = t2.x - t1.x;
    c = t1.x * t2.y - t2.x * t1.y;
    }
};

bool intersect(const line &l1, const line &l2, t &res) {
    if (l1.a * l2.b == l2.a * l1.b)
    return false;
    double g = l1.a * l2.b - l2.a * l1.b;
    res.x = -(l1.c * l2.b - l2.c * l1.b) / g;
    res.y = -(l1.a * l2.c - l2.a * l1.c) / g;
    return true;
}

int main() {

    t x0, x1, x2, x3, m; // m точка пересечения

    double h = 6, answer = 0;

    cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;
    double x0x1_d = x0.distance(x1);
    if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {
        if (x0.t_is_line_segment(x2, x3)) {
            if (x1.t_is_line_segment(x2, x3)) {
                if (x0x1_d <= h) {
                    answer = M_PI * x0x1_d/2;
                } else {
                    answer = x0x1_d * asin(h / x0x1_d);
                }
            } else {
                if (x2.t_is_line_segment(x1, x3)) { 
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));
                                            }
                                } else {
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));
                                            }
                }
            }
        } else {
            double a;
            if (x1.t_is_line_segment(x2, x3)) {
                a = min(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * acos(a / x0x1_d);
                } else {
                    answer = x0x1_d * asin(a / x0x1_d);
                }
            } else {
                a = max(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));
                }
            }
        }
    } else {
        line l10(x0, x1), l23(x2, x3);
        if (intersect(l10, l23, m)) {
            if (m.t_is_line_segment(x2, x3)) {
                double x0m_d = m.distance(x0);
                answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);
                if (answer > h) answer = h;
            }
        }
    }
    cout << fixed << setprecision(3) << answer << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cmath>

#include <iomanip>

#include <iostream>

using namespace std;

struct t {

double x, y;

t() {

x = 0;

y = 0;

}

t(double x, double y) {

this->x = x;

this->y = y;

}

t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }

t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

bool operator!=(t &p) { return !(*this == p); }

bool t_is_line_segment(t &t1, t &t2) {

t t3 = *this;

t a = t2 - t1;

t b = t3 - t1;

double sa = a.x * b.y - b.x * a.y;

if (sa > 0.0) return false;

if (sa < 0.0) return false;

if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;

if (a.length() < b.length()) return false;

if (t1 == t3) return false;

if (t2 == t3) return false;

return true;

}

double distance(const t &p) {

double a = this->x - p.x;

double b = this->y - p.y;

return sqrt(a * a + b * b);

}

double length(void) { return sqrt(x * x + y * y); }

};

struct line {

double a, b, c;

line(const t &t1, const t &t2) {

a = t1.y - t2.y;

b = t2.x - t1.x;

c = t1.x * t2.y - t2.x * t1.y;

}

};

bool intersect(const line &l1, const line &l2, t &res) {

if (l1.a * l2.b == l2.a * l1.b)

return false;

double g = l1.a * l2.b - l2.a * l1.b;

res.x = -(l1.c * l2.b - l2.c * l1.b) / g;

res.y = -(l1.a * l2.c - l2.a * l1.c) / g;

return true;

}

int main() {

t x0, x1, x2, x3, m; // m точка пересечения

double h = 6, answer = 0;

cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;

double x0x1_d = x0.distance(x1);

if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {

if (x0.t_is_line_segment(x2, x3)) {

if (x1.t_is_line_segment(x2, x3)) {

if (x0x1_d <= h) {

answer = M_PI * x0x1_d/2;

} else {

answer = x0x1_d * asin(h / x0x1_d);

}

} else {

if (x2.t_is_line_segment(x1, x3)) {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));

}

} else {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));

}

} else {

double a;

if (x1.t_is_line_segment(x2, x3)) {

a = min(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * acos(a / x0x1_d);

} else {

answer = x0x1_d * asin(a / x0x1_d);

}

} else {

a = max(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));

}

} else {

line l10(x0, x1), l23(x2, x3);

if (intersect(l10, l23, m)) {

if (m.t_is_line_segment(x2, x3)) {

double x0m_d = m.distance(x0);

answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);

if (answer > h) answer = h;

}

cout << fixed << setprecision(3) << answer << endl;

return 0;

}

Решение задачи

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]H[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]H[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]H[/latex]

в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1.[latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1. [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times \arcsin \frac{X_0 X_3} {X_0 X_1} [/latex]

1.1.2.1.2. [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

1.1.2.1.2.1. [latex]X_0 X_1 < \sqrt{X_0 X_2^2 + H^2} [/latex]

В таком случае искомая величина равна дуге [latex]MN[/latex]= [latex]X_0 X_1 \times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{X_0 X_3} {X_0 X_1}))

1.1.2.2. данный случай аналогичен предыдущему.Единственное различие заключается в том,что точки [latex]X_2[/latex] и [latex]X_3[/latex] меняются местами в формулах.

1.2 [latex]Х_0[/latex] не принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.2.1 [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times \arccos \frac{A}{X_0 X_1}[/latex]

1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times \arcsin \frac{A}{X_0 X_1}[/latex]

1.2.2. обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.2.2.1. [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{A}{X_0 X_1})[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.

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

Ссылки

Условие задачи на сайте e-olymp
Код решения

Related Images:

Похожее

One thought on “e-olymp 12. Поврежденная картина”

Мазурок Игорь Евгеньевич says: 21/01/2018 at 17:00

Очень детальный разбор вариантов. Молодец. Но есть замечания.
— Начну с самой большой ошибки. Для создания чертежей нужно было рассчитать координаты и написать несколько строчек SVG. Вместо этого Вы оттачивали навыки тыканья мышкой в Adobe Illustrator. Этот навык не для программиста и оценивать его я не буду. Тем более, что линии пересекаются не в точках, а как попало — .
— Надписи на рисунках должны выглядеть как в тексте. Т.е. наклонными и с индексами.
— Зачем оставлять так много пустого пространства выше и ниже рисунков?
— В формулах арксинус и арккосинус должны быть написаны прямым шрифтом, как и обычный синус и косинус.
— Н не везде формула?
— Случай 1.1.2.2 будет работать если высота стержня настолько велика, что верхушка вообще не коснётся картины?
— Пробелы между словами нужны даже если они в скобках.
— Поправьте, пожалуйста, отступы по крайней мере в 44-й и 70-й строках.

Войдите, чтобы ответить