e-olymp 396. Дождь

24/11/2021 by Александр Мармалюк

Условие

Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Напишите программу, которая по координате $\ x_0\ $ точки появления капли над землей вычисляет координату $x$ точки соприкосновения капли с землей $\ \left(y = 0\right).\ $ Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $\ x_0\ $ точки появления капли $\ \left( 0 \lt x_0 \lt 10000\right)\ $ и количество отрезков-препятствий $\ N\ (0 \leqslant N \leqslant 100).\ $ Далее следует $\ N\ $ строк, каждая из которых содержит четыре разделенные пробелами числа $\ x_1,\ $ $\ y_1,\ $ $\ x_2,\ $ $\ y_2\ $ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $\ 0$\ до $\ 10000\ $, $\ x_1 \lt x_2,$ $y_1 \neq y_2.\ $ Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $\ x\ $ точки соприкосновения капли с землей.

Тесты

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

30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
7 5 1 6 10 8 5 3 8 2 6 10 11 9 9 10 14 12 6 6 12 7	8
4 4 1 1 3 3 2 3 0 6 7 3 5 2 6 5 9 6	4
8 3 8 6 2 4 7 4 9 3 6 1 10 2	2
2 3 5 9998 0 10000 7 9996 11 9994 4 9996 9 9993	9

Код программы

#include <iostream>
#include <cmath>
#include <vector>
#define MAX_Y 10000;
using namespace std;
struct slide {
    double x1;
    double y1;
    double x2;
    double y2;
};
//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]
double f (slide x, double x0) {
    double dx = x.x2 - x.x1;
    double dy = x.y2 - x.y1;
    return ((dy*(x0 - x.x1))/dx + x.y1);
}
vector <slide> roof; //вектор всех крыш
//считывание и заполнение данных
void read (int n) {
    while (n--) {
        double a, b, c, d;
        slide x;
        cin >> a >> b >> c >> d;
        if (a < c) {
            x.x1 = a;
            x.y1 = b;
            x.x2 = c;
            x.y2 = d;
        }
        else
        {
            x.x1 = c;
            x.y1 = d;
            x.x2 = a;
            x.y2 = b;
        }
        roof.push_back(x);
    }
}
int main() {
    int n, x, y = MAX_Y + 1;
    slide a;
    cin >> x >> n;
    if (n == 0) {
        cout << x;
        return 0;
    }
    read (n);
    while (roof.size()) {
        int index = -1;
        int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей
        bool no_projection = true;
        for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х
            if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?
                no_projection = false;
                if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?
                    value = f(roof[i], x);
                    index = i;
                }
            }
            if (min(roof[i].y1, roof[i].y2) > y) {  //крыша целиком осталась выше?
                roof.erase(roof.begin() + i);
                i--;
            }
        }
        if ((roof.size() == 0) or (no_projection)) {  //если удалили все крыши или свободно падает на землю
            cout << x;
            return 0;
        }
        if (roof[index].y1 < roof[index].y2)  //какой конец крыши ниже?
            x = roof[index].x1;
        else
            x = roof[index].x2;
        y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату
        roof.erase(roof.begin() + index);
    }
    cout << x;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

#define MAX_Y 10000;

using namespace std;

struct slide {

double x1;

double y1;

double x2;

double y2;

};

//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]

double f (slide x, double x0) {

double dx = x.x2 - x.x1;

double dy = x.y2 - x.y1;

return ((dy*(x0 - x.x1))/dx + x.y1);

}

vector <slide> roof; //вектор всех крыш

//считывание и заполнение данных

void read (int n) {

while (n--) {

double a, b, c, d;

slide x;

cin >> a >> b >> c >> d;

if (a < c) {

x.x1 = a;

x.y1 = b;

x.x2 = c;

x.y2 = d;

}

else

{

x.x1 = c;

x.y1 = d;

x.x2 = a;

x.y2 = b;

}

roof.push_back(x);

}

int main() {

int n, x, y = MAX_Y + 1;

slide a;

cin >> x >> n;

if (n == 0) {

cout << x;

return 0;

}

read (n);

while (roof.size()) {

int index = -1;

int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей

bool no_projection = true;

for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х

if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?

no_projection = false;

if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?

value = f(roof[i], x);

index = i;

}

if (min(roof[i].y1, roof[i].y2) > y) { //крыша целиком осталась выше?

roof.erase(roof.begin() + i);

i--;

}

if ((roof.size() == 0) or (no_projection)) { //если удалили все крыши или свободно падает на землю

cout << x;

return 0;

}

if (roof[index].y1 < roof[index].y2) //какой конец крыши ниже?

x = roof[index].x1;

else

x = roof[index].x2;

y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату

roof.erase(roof.begin() + index);

}

cout << x;

return 0;

}

Решение

Для удобства создадим структуру slide, которая будет описывать координаты концов отрезка-крыши. Также будем считать, что первый конец отрезка находится левее (для этого будем менять местами точки в случае необходимости).
Будем представлять каждую крышу как отрезок прямой на плоскости. Для этого применим уравнение прямой по двум точкам, принадлежащим этой прямой:
$$\frac{x — x_1}{x_2 — x1}=\frac{y — y_1}{y_2 — y_1}$$
Чтобы проверить, может ли капля в текущий момент проектироваться на некоторую крышу, надо проверить, находится ли абсцисса капли между абсциссами концов отрезка-крыши, а также найти ту крышу, которая в абсциссе капли «выше всех» (другими словами, у какой из прямых, которым принадлежат те отрезки, на которые проектируется капля, наибольшее значение ординаты в абсциссе капли). Для этого создадим функцию, которая и будет возвращать искомое значение ординаты. Также важно убедиться в том, что эта крыша находится ниже текущего положения капли. Заметим, что если некоторая крыша целиком находится выше капли, то мы на неё уже никогда не попадем, поэтому её нужно удалить из вектора. Найдя нужную крышу, определим новые координаты капли после того, как она скатится по этой крыше. Если капля в свободном падении и на её пути больше нет препятствий (крыш не осталось или нет такой, на которую проектируется капля), то текущая абсцисса капли и будет ответом на задачу.

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

Related Images:

e-olymp 497. Лентяй

21/05/2019 by Андрей Зиновьев

Задача

Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

Выходные данные:
Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

Тесты

Входные данные	Вывод программы
2 1 1 2 2 1 2 3 4	YES NO
1 1 5 6	YES
2 2 1 4 7 9 3 1 30 2 5 5 10	NO YES

Continue reading →

Related Images:

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

13/01/2018 by Андрей Святозар Чернецкий

Задача

Римская цифра [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:

Ю2.7

04/10/2014 by Фесенко Катерина Володимирівна

Задача.

Треугольник и круги.

Лежит ли заданный на плоскости треугольник АВС в области пересечения заданных кругов:

[latex](x-a1)^2+(y-b1)^2<r1^2[/latex] , и [latex](x-a2)^2+(y-b2)^2<r2^2[/latex] ?

#include <iostream>
#include <math.h>
using namespace std;


int main(){
	int a1, b1, r1;
	int a2, b2, r2;
	int ax, bx, cx;
	int ay, by, cy;
	cin >> a1 >> b1 >> r1;
	cin >> a2 >> b2 >> r2;
	cin >> ax >> bx >> cx;
	cin >> ay >> by >> cy;
	if ( ((ax-a1)*(ax-a1)+(ay-b1)*(ay-b1)<r1*r1)&&
	   ((bx-a1)*(bx-a1)+(by-b1)*(by-b1)<r1*r1)&&
	   ((cx-a1)*(cx-a1)+(cy-b1)*(cy-b1)<r1*r1)&&
	   ((ax-a2)*(ax-a2)+(ay-b2)*(ay-b2)<r2*r2)&&
	   ((bx-a2)*(bx-a2)+(by-b2)*(by-b2)<r2*r2)&&
	   ((cx-a2)*(cx-a2)+(cy-b2)*(cy-b2)<r2*r2))
	{
	     printf ("На пересечении");
	}
	else
	{
             printf ("Не на пересечении");
	}
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main(){

int a1, b1, r1;

int a2, b2, r2;

int ax, bx, cx;

int ay, by, cy;

cin >> a1 >> b1 >> r1;

cin >> a2 >> b2 >> r2;

cin >> ax >> bx >> cx;

cin >> ay >> by >> cy;

if ( ((ax-a1)*(ax-a1)+(ay-b1)*(ay-b1)<r1*r1)&&

((bx-a1)*(bx-a1)+(by-b1)*(by-b1)<r1*r1)&&

((cx-a1)*(cx-a1)+(cy-b1)*(cy-b1)<r1*r1)&&

((ax-a2)*(ax-a2)+(ay-b2)*(ay-b2)<r2*r2)&&

((bx-a2)*(bx-a2)+(by-b2)*(by-b2)<r2*r2)&&

((cx-a2)*(cx-a2)+(cy-b2)*(cy-b2)<r2*r2))

{

printf ("На пересечении");

}

else

{

printf ("Не на пересечении");

}

return 0;

}

Ссылка на программу на С++: http://ideone.com/NYTAWN

Код программы на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) {
		Scanner in=new Scanner(System.in);
		int a1=in.nextInt();
		int b1=in.nextInt();
		int r1=in.nextInt();
		int a2=in.nextInt();
		int b2=in.nextInt();
		int r2=in.nextInt();
		int ax=in.nextInt();
		int bx=in.nextInt();
		int cx=in.nextInt();
		int ay=in.nextInt();
		int by=in.nextInt();
		int cy=in.nextInt();
	if ( ((ax-a1)*(ax-a1)+(ay-b1)*(ay-b1)<r1*r1)&&
	   ((bx-a1)*(bx-a1)+(by-b1)*(by-b1)<r1*r1)&&
	   ((cx-a1)*(cx-a1)+(cy-b1)*(cy-b1)<r1*r1)&&
	   ((ax-a2)*(ax-a2)+(ay-b2)*(ay-b2)<r2*r2)&&
	   ((bx-a2)*(bx-a2)+(by-b2)*(by-b2)<r2*r2)&&
	   ((cx-a2)*(cx-a2)+(cy-b2)*(cy-b2)<r2*r2))
	{
	    System.out.printf("На пересечении");
	}
	else
	{
        System.out.printf("Не на пересечении");
	}	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) {

Scanner in=new Scanner(System.in);

int a1=in.nextInt();

int b1=in.nextInt();

int r1=in.nextInt();

int a2=in.nextInt();

int b2=in.nextInt();

int r2=in.nextInt();

int ax=in.nextInt();

int bx=in.nextInt();

int cx=in.nextInt();

int ay=in.nextInt();

int by=in.nextInt();

int cy=in.nextInt();

if ( ((ax-a1)*(ax-a1)+(ay-b1)*(ay-b1)<r1*r1)&&

((bx-a1)*(bx-a1)+(by-b1)*(by-b1)<r1*r1)&&

((cx-a1)*(cx-a1)+(cy-b1)*(cy-b1)<r1*r1)&&

((ax-a2)*(ax-a2)+(ay-b2)*(ay-b2)<r2*r2)&&

((bx-a2)*(bx-a2)+(by-b2)*(by-b2)<r2*r2)&&

((cx-a2)*(cx-a2)+(cy-b2)*(cy-b2)<r2*r2))

{

System.out.printf("На пересечении");

}

else

{

System.out.printf("Не на пересечении");

}

Ссылка на программу на Java:http: //ideone.com/QZ7RB1

Решение:

Поскольку все фигуры выпуклые достаточно проверить вершины треугольника. Подставляем координаты всех трёх вершин в оба неравенства. Если все условия удовлетворены, то лежит. Если хоть одно условие не выполняется, то не лежит.

Тест

a1	b1	r1	a2	b2	r2	ax	bx	cx	ay	by	cy	Принадлежит?
1	2	3	3	4	5	6	7	8	6	7	4	нет
1	2	15	3	4	12	6	7	8	6	7	4	да
7	5	10	4	6	16	6	7	3	5	6	7	да
7	5	5	4	6	3	6	7	3	5	6	7	нет

Related Images:

Ю 3.4

19/09/2014 by Іванов Вячеслав Володимирович

Задача: Прямоугольник на плоскости [latex]a \le x \le b, \quad c \le y \le d[/latex] задаётся четырьмя числами (его габаритами): [latex]a, b, c, d.[/latex] Последовательно вводятся габариты [latex]n[/latex] прямоугольников. В процессе ввода находить площадь их пересечения, не запоминая самих габаритов.

NI — «no intersection» — нет общего сегмента

№	[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]S[/latex]	Комментарий
1	-5	-3	1	4	NI	Пройден: нет общего интервала
-2	0	1	4
2	0	4.5	1.2	4.6	NI	Пройден: нет общего интервала
2	4	5	7.4
3	2	5	1	4	NI	Пройден: общая сторона не считается пересечением, т.к. даёт нулевую площадь
5	6	1	4
4	2	4	2	4	4	Пройден
2	4	2	4
5	2	5	1	4	NI	Пройден: не все данные прямоугольники имеют общий сегмент
0	3	2	3
6	7	3	5
6	0	7	0	3	1	Пройден
2	6	1	5
3	5	2	5
4	8	2	3

#include 
#include 
//sort pairs of coordinates by value
void sbv(double &x1, double &x2, double &y1, double &y2)
{
    if( x1 > x2 ) std::swap( x1 , x2 );
    if( y1 > y2 ) std::swap( y1 , y2 );
}
//find whether the rectangles intersect
bool intersect( double b1, double e1, double b2, double e2 )
{
    //"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis)
    if( b2 >= e1 || e2 <= b1 ) return false;
    return true;
}

int main()
{
    double a, b, c, d; //meaningful coodinates of rectangle sides
    int n; scanf( "%d", &n );
    scanf( "%lg %lg %lg %lg", &a, &b, &c, &d );
    double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area
    for( int i=1; i<n; i++ )
    {
        scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords.
        if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect
        {
            sbv( a, x1, x2, b ); //sort again to find the inner points
            sbv( c, y1, y2, d ); //(image is attached)
            printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) );
        }
        else
        {
            printf("System of rectangles has no common area.\n");
            break;
        }

    }
    return 0;
}

#include

//sort pairs of coordinates by value

void sbv(double &x1, double &x2, double &y1, double &y2)

{

if( x1 > x2 ) std::swap( x1 , x2 );

if( y1 > y2 ) std::swap( y1 , y2 );

}

//find whether the rectangles intersect

bool intersect( double b1, double e1, double b2, double e2 )

{

//"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis)

if( b2 >= e1 || e2 <= b1 ) return false;

return true;

}

int main()

{

double a, b, c, d; //meaningful coodinates of rectangle sides

int n; scanf( "%d", &n );

scanf( "%lg %lg %lg %lg", &a, &b, &c, &d );

double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area

for( int i=1; i<n; i++ )

{

scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords.

if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect

{

sbv( a, x1, x2, b ); //sort again to find the inner points

sbv( c, y1, y2, d ); //(image is attached)

printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) );

}

else

{

printf("System of rectangles has no common area.\n");

break;

}

return 0;

}

Алгоритм решения:
1. Для удобства, запрограммировать задачу можно, сведя её к одномерному случаю: рассматривать проекции сторон прямоугольников на координатные оси. (см. рис. 1)
2. Проверка на пересечение: данные прямоугольники пересекаются и имеют общую площадь, если их проекции имеют общий интервал значений, больший одной точки.
3. Так как запоминать габариты прямоугольников нельзя по условию, работать будем с габаритами «общего» прямоугольника, которые сохраняются соотв. в переменные [latex]x1 \le x2, y1 \le y2[/latex]. Если новый прямоугольник пересекается с «общим», то определить обновленные габариты общего прямоугольника и рассчитать площадь(см. рис. 2). Если не пересекается, то выполнение программы прерывается, т.к. нужно вывести площадь прямоугольника, общего для всех [latex]n[/latex] прямоугольников.

Значения переменных в условии задачи не ограничены, так что для хранения габаритов был использован тип double, для всех порядковых переменных — тип int.

Протестировать решение можно по ссылке.