e-olymp 7504. Три прямоугольника

19/01/2019 by Николай Козиний

Задача взята с сайта e-olymp

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 0 1 1 1 1 2 2 0 0 2 2	4
2	2 -2 -2 2 -1 -1 1 1 40 40 41 41	17
3	-1 2 2 -1 1 0 4 2 1 0 3 6	21
4	-100 -100 -99 -99 100 100 99 99 -100 -100 100 100	40000
5	3 0 4 1 1 0 3 3 1 0 3 3	7

Решение

Для решения этой задачи создадим структуру «точка» и структуру «прямоугольник». Поскольку для построения прямоугольника достаточно двух точек, структура будет содержать только наименьшую и наибольшую точки прямоугольника. Напишем функции для построения прямоугольника, ввода прямоугольника, вычисления площади прямоугольника, построения пересечения прямоугольников и вычисления площади всех трех прямоугольников. О последних двух стоит написать подробнее.

Для нахождения пересечения прямоугольников рассмотрим проекции координат прямоугольника на координатные оси $x$ и $y$. В случае, если интервалы пересекаются, началом пересечения будет наибольшее из начал интервалов, а концом — наименьшее из их концов. В ином же случае дадим точкам по этой координате одинаковые значения, в результате чего площадь такого прямоугольника и всех пересечений, которые он образует будет равна нулю. Координатами точек пересечения прямоугольников будут, следовательно, соответствующие координаты пересечения интервалов на осях.

После этого задача сводится к написанию функции общей площади. То, что решение, в котором мы просто суммируем площадь трех прямоугольников проходит лишь на один тест, наводит на мысль о том, что мы добавляем площадь пересечений несколько раз. Следовательно, от суммы площадей трех прямоугольников отнимем площадь их пересечения друг с другом и добавим площадь пересечения всех трех(поскольку в случае, если существует пересечение трех, то мы лишний раз отнимаем его площадь).

Записав прямоугольники, в динамический массив, передадим его в функцию нахождения общей площади, и выведем результат.

#include <iostream>
#include <cmath>
using namespace std;
struct point{int x;int y;};
struct rect{point a;point b;};
rect getrect(point a, point b, rect c){
    if(a.x > b.x)swap(a.x,b.x);
    if(a.y > b.y)swap(a.y,b.y);
    c.a = a;
    c.b = b;
    return c;
}
rect getrekt(rect c){
    point a,b;
    cin >> a.x >> a.y >> b.x >> b.y;
    return getrect(a,b,c);
}
int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){
    rect cr;
    point a1,b1;
    a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));
    a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));
    b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));
    b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));
    return getrect(a1,b1,cr);
}
int farea(rect *q){
    return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));
}
int main() {
    rect *q = new rect [3];
    for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);
    cout<<farea(q);
}

#include <iostream>

#include <cmath>

using namespace std;

struct point{int x;int y;};

struct rect{point a;point b;};

rect getrect(point a, point b, rect c){

if(a.x > b.x)swap(a.x,b.x);

if(a.y > b.y)swap(a.y,b.y);

c.a = a;

c.b = b;

return c;

}

rect getrekt(rect c){

point a,b;

cin >> a.x >> a.y >> b.x >> b.y;

return getrect(a,b,c);

}

int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){

rect cr;

point a1,b1;

a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));

a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));

b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));

b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));

return getrect(a1,b1,cr);

}

int farea(rect *q){

return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));

}

int main() {

rect *q = new rect [3];

for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);

cout<<farea(q);

}

Решение. Многомерные массивы

Для решения с помощью многомерных массивов сдвинем все точки так, чтобы они всегда находились в положительной координатной четверти. Далее, заведем массив, значения которого будут соответствовать квадрату длины 1 координатной плоскости. Далее, заполним единицами все квадраты,содержащиеся в прямоугольника. После этого проходим все значения массива и прибавляем 1 к выводимому значению, если элемент массива равен единице.

#include <iostream>
#include <cmath>
#define N 100
using namespace std;
 
int main() {
    int rect[3][4];
    int field[2*N][2*N];
    int count = 0;
    for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;
    for(int i = 0;i < 3;i++){
        for(int k = 0;k < 4;k++){
            cin >> rect[i][k];
            rect[i][k] = rect[i][k] + N;
        }
    }
    for(int k = 0;k<3;k++){
        for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){
            for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){
                field[i][j]=1;
            }
        }
    }
    for(int i = 0;i < 2*N;i++){
        for(int k = 0;k < 2*N;k++){
            if(field[i][k] & 1)count++;
        }
    }
    cout<<count;
}

#include <iostream>

#include <cmath>

#define N 100

using namespace std;

int main() {

int rect[3][4];

int field[2*N][2*N];

int count = 0;

for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;

for(int i = 0;i < 3;i++){

for(int k = 0;k < 4;k++){

cin >> rect[i][k];

rect[i][k] = rect[i][k] + N;

}

for(int k = 0;k<3;k++){

for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){

for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){

field[i][j]=1;

}

for(int i = 0;i < 2*N;i++){

for(int k = 0;k < 2*N;k++){

if(field[i][k] & 1)count++;

}

cout<<count;

}

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

Related Images:

e-olymp 4557. Одинокий король

21/12/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

#	Входные данные	Выходные данные
1	5 1 2 4 7 4	4
2	5 1 2 4 6 4	Ok 2
3	3 1 2 1	Ok 5
4	3 1 5 1	2
5	8 8 8 8 8 8 8 8 8	Ok 8

Код

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

int main() {
    int *x, *y, n, pos, x1 = 0, y1 = 0;
    bool f = true;
    cin >> n;
    x = new int [n];
    y = new int [n];
    for (int i = 1; i <= n; i ++){
        cin >> pos;
        if (pos == 1){
            x1 -= 1;
            y1 += 1;
        }
        else if (pos == 2) y1 += 1;
        else if (pos == 3){
            x1 += 1;
            y1 += 1;
        }
        else if (pos == 4) x1 += 1;
        else if (pos == 5){
            x1 += 1;
            y1 -= 1;
        }
        else if (pos == 6) y1 -= 1;
        else if (pos == 7){
            x1 -= 1;
            y1 -= 1;
        }
        else if (pos == 8) x1 -= 1;
        x[i] = x1;
        y[i] = y1;
    }
    for (int i = 1; i < n && f; i++)
        for (int j = 0; j < i; j++)
            if ((x[i] == x[j]) && (y[i] == y[j])){
                cout << i; 
                f = false;
            }
    if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]);
    delete []x;
    delete []y;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int *x, *y, n, pos, x1 = 0, y1 = 0;

bool f = true;

cin >> n;

x = new int [n];

y = new int [n];

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

cin >> pos;

if (pos == 1){

x1 -= 1;

y1 += 1;

}

else if (pos == 2) y1 += 1;

else if (pos == 3){

x1 += 1;

y1 += 1;

}

else if (pos == 4) x1 += 1;

else if (pos == 5){

x1 += 1;

y1 -= 1;

}

else if (pos == 6) y1 -= 1;

else if (pos == 7){

x1 -= 1;

y1 -= 1;

}

else if (pos == 8) x1 -= 1;

x[i] = x1;

y[i] = y1;

}

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

for (int j = 0; j < i; j++)

if ((x[i] == x[j]) && (y[i] == y[j])){

cout << i;

f = false;

}

if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]);

delete []x;

delete []y;

return 0;

}

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива x = new int [n]; и y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле for (int i = 1; i <= n; i ++); заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так: abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

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

int main() {
    int *x, n, pos, x1 = 0, y1 = 0;
    bool f = true;
    cin >> n;
    int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};
    x = new int [2*n+2];
    for (int i = 2; i < (2 * n + 2); i += 2){
        cin >> pos;
        x1 += X[pos-1];
        y1 += Y[pos-1];
        x[i] = x1;
        x[i+1] = y1;
    }
    for (int i = 0; i < (2 * n + 2) && f; i += 2)
        for (int j = 0; j < i; j += 2)
            if ((x[i] == x[j]) && (x[i+1] == x[j+1])){
                cout << i / 2; 
                f = false;
            }
    if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]);
    delete []x;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int *x, n, pos, x1 = 0, y1 = 0;

bool f = true;

cin >> n;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

x = new int [2*n+2];

for (int i = 2; i < (2 * n + 2); i += 2){

cin >> pos;

x1 += X[pos-1];

y1 += Y[pos-1];

x[i] = x1;

x[i+1] = y1;

}

for (int i = 0; i < (2 * n + 2) && f; i += 2)

for (int j = 0; j < i; j += 2)

if ((x[i] == x[j]) && (x[i+1] == x[j+1])){

cout << i / 2;

f = false;

}

if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]);

delete []x;

return 0;

}

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы if(); можно заменить массивами X[]; и Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

#include <iostream>
#include <cmath>
using namespace std;
 
int x[2001][2001];
 
int main() {
    int n;
    cin >> n;
    int pos;
    bool f = true;
    int x1 = 1001, y1 = 1001;
    for (int i = 0; i< n && f; i++){
        cin >> pos;
        if(x[x1][y1] == 1){ 
            cout << i;
            f = false;
        }
        else x[x1][y1] = 1;
        switch (pos){
            case 1: x1--; y1++; break;
            case 3: x1++;
            case 2: y1++; break;
            case 4: x1++; break;
            case 5: x1++;
            case 6: y1--; break;
            case 7: y1--; 
            case 8: x1--;
        }
    }
    if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int x[2001][2001];

int main() {

int n;

cin >> n;

int pos;

bool f = true;

int x1 = 1001, y1 = 1001;

for (int i = 0; i< n && f; i++){

cin >> pos;

if(x[x1][y1] == 1){

cout << i;

f = false;

}

else x[x1][y1] = 1;

switch (pos){

case 1: x1--; y1++; break;

case 3: x1++;

case 2: y1++; break;

case 4: x1++; break;

case 5: x1++;

case 6: y1--; break;

case 7: y1--;

case 8: x1--;

}

if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001);

return 0;

}

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

Засчитанное решение 1 на e-olymp.
Засчитанное решение 2 на e-olymp.
Засчитанное решение 3 на e-olymp.
Код 1 в ideone.
Код 2 в ideone.
Код 3 в ideone.

Related Images:

e-olymp 143. Точка и треугольник

26/12/2017 by Александра Филистович

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

№	Входные данные	Выходные данные
1	2 6 -9 3 8 1 5 11	1
2	-13 10 -12 5 99 80 17 13	0
3	98 -50 -87 7 5 3 23 17	0
4	5 15 7 12 5 3 2 54	1
5	2 2 3 1 1 3 9 11	1

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

#include <iostream>
using namespace std;
 
int main() {
 double x0,x1,x2,x3,y0,y1,y2,y3;
 double z1,z2,z3;
 cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
 z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);
 z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);
 z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);
 if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";
 else cout<<"0";
 return 0;
}

#include <iostream>

using namespace std;

int main() {

double x0,x1,x2,x3,y0,y1,y2,y3;

double z1,z2,z3;

cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;

z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);

z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);

z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);

if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";

else cout<<"0";

return 0;

}

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

Related Images:

e-olymp 72. Дорога домой

26/12/2017 by Павел Жуков

Задача

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]left langle 1,1 right rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]left langle 0,0 right rangle[/latex], а его дом расположен в точке [latex]left langle x_{h},y_{h} right rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0leq n,k,t,vleq 100)[/latex] . Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq x_{h}, y_{h}leq 10^5)[/latex] .

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]7[/latex]	Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex] [latex]15[/latex] [latex]15[/latex]	Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex] [latex]105[/latex] [latex]-105[/latex]	Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex] [latex]40[/latex] [latex]-20[/latex]	Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-24[/latex] [latex]0[/latex]	Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-23[/latex] [latex]0[/latex]	Good night Ia

Первый вариант кода программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long int n, k, t, v, hx, hy;
    long int x = 0, y = 0;
    cin >> n >> k >> t >> v;
    cin >> hx >> hy;
    for(long int i = 0; i <= k; i++){
         if(i%4 == 0){ 
             x += 1 + n*i;
             y += 1 + n*i; 
         } else if (i%4 == 1){ 
             x += 1 + n*i;
             y -= 1 + n*i; 
         } else if(i%4 == 2){
             x -= 1 + n*i; 
             y -= 1 + n*i; 
         } else if(i%4 == 3){ 
             x -= 1 + n*i; 
             y += 1 + n*i; 
         } 
    } 
    if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

long int x = 0, y = 0;

cin >> n >> k >> t >> v;

cin >> hx >> hy;

for(long int i = 0; i <= k; i++){

if(i%4 == 0){

x += 1 + n*i;

y += 1 + n*i;

} else if (i%4 == 1){

x += 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 2){

x -= 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 3){

x -= 1 + n*i;

y += 1 + n*i;

}

if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

Второй вариант кода программы

#include <iostream>
using namespace std;

int main() {
    long int n, k, t, v, hx, hy;
    cin >> n >> k >> t >> v >> hx >> hy;
    long int s1, s2, s3, s4;
    long int m1, m2, m3, m4;
    m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m4 = (k + 1) / 4;
    s1 = (1 + (m1 - 1) * 2 * n) * m1;
    s2 = (1 + n + 2 * n * (m2 - 1)) * m2;
    s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;
    s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;
    long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;
    if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

cin >> n >> k >> t >> v >> hx >> hy;

long int s1, s2, s3, s4;

long int m1, m2, m3, m4;

m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m4 = (k + 1) / 4;

s1 = (1 + (m1 - 1) * 2 * n) * m1;

s2 = (1 + n + 2 * n * (m2 - 1)) * m2;

s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;

s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;

long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;

if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

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

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]sumlimits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = begin{cases} left langle1 + xy, 1 + xyright rangle & textit{if } xvdots 4 = 0 \ left langle1 + xy, (-1) cdot (1 + xy)right rangle & textit{if } xvdots 4 = 1 \ left langle(-1) cdot (1 + xy), (-1) \cdot (1 + xy)right rangle & textit{if } xvdots 4 = 2 \ left langle(-1) cdot (1 + xy), 1 + xyright rangle & textit{if } xvdots 4 = 3 end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{i=0}^k f(i, n)[/latex] — это вектор [latex]left langle a,b right rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]left langle a,b right rangle[/latex] и вектора [latex]left langle x_{h},y_{h} right rangle[/latex]:

$$sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]left langle 0,0 right rangle[/latex] и [latex]left langle 1,1 right rangle[/latex], то есть — [latex]sqrt{2}[/latex].

$$ sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = displaystylefrac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n Rightarrow S_{1}=frac{1 + 1 +4n(m_1-1)}{2}Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=2$ иначе, $m_2=displaystylefrac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=3$ иначе, $m_3=displaystylefrac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{k+1}{4}$

Тогда, для вычисления координат [latex]left langle x,y right rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

Условие задачи на e-olymp
Код решения первого варианта на ideone.com
Код решения второго варианта на ideone.com

Related Images:

There is no Spoon — Episode 1

15/04/2017 by Вадим Гордийчук

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

You give an incorrect neighbor for a node.
You give the neighbors for an empty cell.
You compute the same node twice.
You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:

( x1, y1) the coordinates of a node.
( x2, y2) the coordinates the closest neighbor on the right of the node.
( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input	Output
2 2 00 0.	0 0 1 0 0 1 1 0 -1 -1 -1 -1 0 1 -1 -1 -1 -1
4 4 .0.. .000 000. ..0.	1 0 -1 -1 1 1 1 1 2 1 1 2 2 1 3 1 2 2 3 1 -1 -1 -1 -1 0 2 1 2 -1 -1 1 2 2 2 -1 -1 2 2 -1 -1 2 3 2 3 -1 -1 -1 -1

The code of the program

#include <iostream>
#include <string>
using namespace std;

int main()
{
    short width; // the number of cells on the X axis
    cin >> width; cin.ignore();
    short height; // the number of cells on the Y axis
    cin >> height; cin.ignore();
    string *node = new string[height];
    short x, y;
    for (y = 0; y < height; ++y)
    {
        getline(cin, node[y]);
    }
    for (y = 0; y < height; ++y)
    {
        for (x = 0; x < width; ++x)
        {
            if (node[y][x] == '0')
            {
                cout << x << ' ' << y << ' ';
                short x2, y2, ansX = -1, ansY = -1;
                for (x2 = x+1; x2 < width; ++x2)
                {
                    if (node[y][x2] == '0')
                    {
                        ansX = x2;
                        ansY = y;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << ' ';
                ansX = -1; ansY = -1;
                for (y2 = y+1; y2 < height; ++y2)
                {
                    if (node[y2][x] == '0')
                    {
                        ansX = x;
                        ansY = y2;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << '\n';
                x = x2-1;
            }
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

short width; // the number of cells on the X axis

cin >> width; cin.ignore();

short height; // the number of cells on the Y axis

cin >> height; cin.ignore();

string *node = new string[height];

short x, y;

for (y = 0; y < height; ++y)

{

getline(cin, node[y]);

}

for (y = 0; y < height; ++y)

{

for (x = 0; x < width; ++x)

{

if (node[y][x] == '0')

{

cout << x << ' ' << y << ' ';

short x2, y2, ansX = -1, ansY = -1;

for (x2 = x+1; x2 < width; ++x2)

{

if (node[y][x2] == '0')

{

ansX = x2;

ansY = y;

break;

}

cout << ansX << ' ' << ansY << ' ';

ansX = -1; ansY = -1;

for (y2 = y+1; y2 < height; ++y2)

{

if (node[y2][x] == '0')

{

ansX = x;

ansY = y2;

break;

}

cout << ansX << ' ' << ansY << '\n';

x = x2-1;

}

import java.util.*;
import java.io.*;
import java.math.*;

class Player
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        short width = in.nextShort(); // the number of cells on the X axis
        short height = in.nextShort(); // the number of cells on the Y axis
        
        if (in.hasNextLine()) {
            in.nextLine();
        }

        String node[] = new String[height];
        
        for(short y = 0; y < height; ++y)
        {
            node[y] = in.nextLine();
        }
        
        for(short y = 0; y < height; ++y)
        {
            for(short x = 0; x < width; ++x)
            {
                if (node[y].charAt(x) == '0')
                {
                    out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");
                    short x2, y2, ansX = -1, ansY = -1;
                    for (x2 = (short)(x+1); x2 < width; ++x2)
                    {
                        if (node[y].charAt(x2) == '0')
                        {
                            ansX = x2;
                            ansY = y;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");
                    ansX = -1;
                    ansY = -1;
                    
                    for(y2 = (short)(y+1); y2 < height; ++y2)
                    {
                        if (node[y2].charAt(x) == '0')
                        {
                            ansX = x;
                            ansY = y2;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");
                    x = (short)(x2-1);
                }
            }
        }
        out.flush();
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

short width = in.nextShort(); // the number of cells on the X axis

short height = in.nextShort(); // the number of cells on the Y axis

if (in.hasNextLine()) {

in.nextLine();

}

String node[] = new String[height];

for(short y = 0; y < height; ++y)

{

node[y] = in.nextLine();

}

for(short y = 0; y < height; ++y)

{

for(short x = 0; x < width; ++x)

{

if (node[y].charAt(x) == '0')

{

out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");

short x2, y2, ansX = -1, ansY = -1;

for (x2 = (short)(x+1); x2 < width; ++x2)

{

if (node[y].charAt(x2) == '0')

{

ansX = x2;

ansY = y;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");

ansX = -1;

ansY = -1;

for(y2 = (short)(y+1); y2 < height; ++y2)

{

if (node[y2].charAt(x) == '0')

{

ansX = x;

ansY = y2;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");

x = (short)(x2-1);

}

out.flush();

}

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Related Images:

Площадь поверхности

11/12/2016 by Тимур Фирсов

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

№	[latex]f\left( x, y\right)[/latex]	Входные данные					Выходные данные
		[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]h[/latex]	[latex]S[/latex]
1	[latex]x+y[/latex]	-10	10	-10	10	0.001	692.82
2	[latex]\left\| x \right\| +\left\| y \right\|[/latex]	-2	2	-2	2	0.005	27.7128
3	[latex]1[/latex]	0	100	0	100	0.1	10000
4	[latex]{x}^{2}+{y}^{2}[/latex]	-1	1	-1	1	0.0005	7.44626

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

#include <iostream>
#include <cmath>
using namespace std;
double z(double x, double y){
    return abs(x)+abs(y);//<-- место для ввода функции z=f(x, y).
}
double dl(double x, double y, double z){
    return sqrt(x*x+y*y+z*z);//Длина вектора.
}
double ras(double xi, double xj, double yi, double yj){
    double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0;
    zii=z(xi, yi); //Найдём координату z каждой вершины треугольников.
    zjj=z(xj, yj);
    zij=z(xi, yj);
    zji=z(xj, yi);
    v1x=(yi-yj)*(zji-zii);  //Вычислим векторное произведение векторов.
    v1y=(zii-zij)*(xj-xi);
    v1z=(yj-yi)*(xj-xi);
    v2x=(yj-yi)*(zji-zjj);
    v2y=(zjj-zij)*(xi-xj);
    v2z=(yi-yj)*(xi-xj);
    return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.
}

int main(){
    double xi, xj, yi, yj, s=0, h;
    int a, b, c, d;
    cin >> a >> b >> c >> d >> h;
    xi = a;
    while(xi<=(b-h)){
        yi=c;
        xj=xi+h;
        while(yi<(d-h)){
            yj=yi+h;
            s+=ras(xi,xj,yi,yj);
            yi=yj;
        }
        xi=xj;
    }
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double z(double x, double y){

return abs(x)+abs(y);//<-- место для ввода функции z=f(x, y).

}

double dl(double x, double y, double z){

return sqrt(x*x+y*y+z*z);//Длина вектора.

}

double ras(double xi, double xj, double yi, double yj){

double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0;

zii=z(xi, yi); //Найдём координату z каждой вершины треугольников.

zjj=z(xj, yj);

zij=z(xi, yj);

zji=z(xj, yi);

v1x=(yi-yj)*(zji-zii); //Вычислим векторное произведение векторов.

v1y=(zii-zij)*(xj-xi);

v1z=(yj-yi)*(xj-xi);

v2x=(yj-yi)*(zji-zjj);

v2y=(zjj-zij)*(xi-xj);

v2z=(yi-yj)*(xi-xj);

return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.

}

int main(){

double xi, xj, yi, yj, s=0, h;

int a, b, c, d;

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

xi = a;

while(xi<=(b-h)){

yi=c;

xj=xi+h;

while(yi<(d-h)){

yj=yi+h;

s+=ras(xi,xj,yi,yj);

yi=yj;

}

xi=xj;

}

cout<<s;

return 0;

}

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах. Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex] Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

Модифицируем данную программу для нахождения приблизительной площади поверхности, заданной функцией с корнем чётной степени.

Тесты

№	[latex]f\left( x, y\right)[/latex]	[latex]z_0[/latex]	Входные данные					Выходные данные
			[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]h[/latex]	[latex]S[/latex]
1	[latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]1[/latex]	-1	1	-1	1	0.00011	6.28734
2	[latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]7y[/latex]	-1	1	-1	1	0.00011	23.0803
3	[latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex]	[latex]0[/latex]	-1	1	-2	2	0.00015	8.08214
4	[latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]-1[/latex]	-2	2	-2	2	0.0005	12.5835

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

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

double z(double x,  double y,  double &z0){
    z0=7*y; //<-- место для ввода слагаемых функции f(x, y) не под корнем чётной степени.
    return (1-x*x-y*y)<0? z0:sqrt(1-x*x-y*y)+z0;//<-- место для ввода функции z=f(x, y).
}
long double  dl(double x,  double y,  double z){
    return sqrt(x*x+y*y+z*z);//Длина вектора.
}
double ras(double xi,  double xj,  double yi,  double yj){
    double zii,  zjj,  zij,  zji,  v1x=0,  v1y=0,  v1z=0,  v2x=0,  v2y=0,  v2z=0,  z0=0;
    zii=z(xi,  yi,  z0); //Найдём координату z каждой вершины треугольников.
    zjj=z(xj,  yj,  z0);
    zij=z(xi,  yj,  z0);
    zji=z(xj,  yi,  z0);
    if(z(xi,  yi,  z0)!=z0||z(xi,  yj,  z0)!=z0||z(xj,  yi,  z0)!=z0){//Используем функцию z(),  потому что z0 может оказаться переменной.
        v1x=(yj-yi)*(zji-zii);  //Вычислим векторное произведение векторов.
        v1y=(zij-zii)*(xj-xi);
        v1z=(yi-yj)*(xj-xi);
    }
    if(z(xj,  yj,  z0)!=z0||z(xi,  yj,  z0)!=z0||z(xj,  yi,  z0)!=z0){
        v2x=(yi-yj)*(zji-zjj);
        v2y=(zij-zjj)*(xi-xj);
        v2z=(yj-yi)*(xi-xj);
    }
    return (dl(v1x,  v1y,  v1z)+dl(v2x,  v2y,  v2z))/2;//Найдём площадь треугольников.
}

int main(){
    double xi,  xj,  yi,  yj,  s=0,  h,  z0=0;
    int a,  b,  c,  d;
    cin >> a >> b >> c >> d >> h;
    xi = a;
    while(xi<=(b-h)){
        yi=c;
        xj=xi+h;
        while(yi<=(d-h)){
            yj=yi+h;
            s+=ras(xi, xj, yi, yj);
            yi=yj;
        }
        xi=xj;
    }
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double z(double x, double y, double &z0){

z0=7*y; //<-- место для ввода слагаемых функции f(x, y) не под корнем чётной степени.

return (1-x*x-y*y)<0? z0:sqrt(1-x*x-y*y)+z0;//<-- место для ввода функции z=f(x, y).

}

long double dl(double x, double y, double z){

return sqrt(x*x+y*y+z*z);//Длина вектора.

}

double ras(double xi, double xj, double yi, double yj){

double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0, z0=0;

zii=z(xi, yi, z0); //Найдём координату z каждой вершины треугольников.

zjj=z(xj, yj, z0);

zij=z(xi, yj, z0);

zji=z(xj, yi, z0);

if(z(xi, yi, z0)!=z0||z(xi, yj, z0)!=z0||z(xj, yi, z0)!=z0){//Используем функцию z(), потому что z0 может оказаться переменной.

v1x=(yj-yi)*(zji-zii); //Вычислим векторное произведение векторов.

v1y=(zij-zii)*(xj-xi);

v1z=(yi-yj)*(xj-xi);

}

if(z(xj, yj, z0)!=z0||z(xi, yj, z0)!=z0||z(xj, yi, z0)!=z0){

v2x=(yi-yj)*(zji-zjj);

v2y=(zij-zjj)*(xi-xj);

v2z=(yj-yi)*(xi-xj);

}

return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.

}

int main(){

double xi, xj, yi, yj, s=0, h, z0=0;

int a, b, c, d;

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

xi = a;

while(xi<=(b-h)){

yi=c;

xj=xi+h;

while(yi<=(d-h)){

yj=yi+h;

s+=ras(xi, xj, yi, yj);

yi=yj;

}

xi=xj;

}

cout<<s;

return 0;

}

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

Related Images:

A60г

31/10/2016 by Алла Марокко

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть u определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^{2}-1, ; \text{ if } (x, y)\in D \\sqrt{\left| x-1 \right| } ; \text{ another case }\end{cases}[/latex] (запись [latex] (x, y)\in D [/latex] означает, что точка с координатами [latex]x, y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y.[/latex] Определить [latex]u.[/latex]

Тесты:

№	Вход		Выход
	[latex]x[/latex]	[latex]y[/latex]	[latex]u[/latex]
1	0.3	0.3	0.836660
2	1	1	0.000000
3	2	2	1.000000
4	0	0	-1.000000

Код на языке C++:

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

int main() {
    float x, y, u;
    scanf("%f%f", &x, &y);
    float a=x*x+y*y;
    if((y<0)||(a>1)||((x>0)&&(a<0.3)))
    {
        printf("u=%f", sqrt(abs(x-1)));
    }
    else
    {
        printf("u=%f",x*x-1);
    }

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

float x, y, u;

scanf("%f%f", &x, &y);

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3)))

{

printf("u=%f", sqrt(abs(x-1)));

}

else

{

printf("u=%f",x*x-1);

}

return 0;

}

Код на языке Java:

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


class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        float x = in.nextFloat();
        float y = in.nextFloat();
        float a=x*x+y*y;
        if((y<0)||(a>1)||((x>0)&&(a<0.3))){
            System.out.println(Math.sqrt(Math.abs(x-1)));
        }
        else{
            System.out.println(x*x-1);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

float x = in.nextFloat();

float y = in.nextFloat();

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3))){

System.out.println(Math.sqrt(Math.abs(x-1)));

}

else{

System.out.println(x*x-1);

}

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex] y<0 [/latex].Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3 .
Ссылки:
Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .

Related Images:

Mif 17.14

07/10/2015 by Холодков Юрий

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex] y[/latex]) фигуре на рисунке? Вариант 14. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Задача взята здесь.

Тесты

[latex]x[/latex]	[latex] y[/latex]	Ответ
-2	4	Принадлежит
4	8	Не принадлежит
-7	9	Не принадлежит
0	0	Не принадлежит
0	1	Принадлежит
4	1	Принадлежит
-7	1	Принадлежит

Код

#include <iostream>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    if ( (y <= 7) && (y >= 1) && (y - 2*x <= 15) && (y + 2*x <= 15))
    {cout << "Принадлежит";}
        else {cout << "Не принадлежит";}
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y;

cin >> x >> y;

if ( (y <= 7) && (y >= 1) && (y - 2*x <= 15) && (y + 2*x <= 15))

{cout << "Принадлежит";}

else {cout << "Не принадлежит";}

return 0;

}

Решение

Каждая из сторон тарпеции делит плоскость на 2 части. Сторона имеет вид [latex]y = k*x + b[/latex]. Путем подстановки были найдены коефициенты [latex] k [/latex] и [latex] b [/latex]. Точка может лежать либо ниже, либо выше, либо на стороне. Если [latex]y — k*x <= b[/latex], точка лежит на или ниже стороны. Основы трапеции представлены в виде [latex] y =1 [/latex] и [latex] y = 7 [/latex].

Ссылка на ideone.com

Related Images:

Mif 17.7

05/10/2015 by Станислав Коциевский

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат
-6	3	принадлежит
0	0	не принадлежит
2	-4	не принадлежит
— 1	2	принадлежит
-5	-2	принадлежит

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

#include <iostream>
using namespace std;
 
int main()
{
    double x, y;
    cin>>x>>y;
    cout<<(((x<=-1)&&(x>=-6)&&(y>=2)&&(y<=7))||((x<=-3)&&(x>=-6)&&(y>=-3)&&(y<=2))?"принадлежит":"не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

double x, y;

cin>>x>>y;

cout<<(((x<=-1)&&(x>=-6)&&(y>=2)&&(y<=7))||((x<=-3)&&(x>=-6)&&(y>=-3)&&(y<=2))?"принадлежит":"не принадлежит");

return 0;

}

Решение.

В данной задаче необходимо проверить подходят ли координаты точки под условия, описывающие фигуру. В этом варианте фигуру можно разбить на 2 прямоугольника. Тогда вышеуказанные условия выглядит так: [latex]-6<=x<=-1[/latex] и [latex]2<=y<=7[/latex] (это первый прямоугольник) или [latex]-6<=x<=-3[/latex] и [latex]-3<=y<=2[/latex] (соответственно, второй прямоугольник).

Здесь находится условие задачи

Ссылка на код на ideone.com

Related Images:

Mif 17.17

04/10/2015 by Сплошнов Кирилл

Условие :

Принадлежит ли точка [latex](x[/latex];[latex]y)[/latex] фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Рисунок :

Тесты :

[latex]x[/latex]	4	-5	0	3	-2.5	1	-3	2	-1.3
[latex]y[/latex]	3	0	-5	-2	-2.5	5	3	-4	2.7
Вывод :	Yes	Yes	Yes	Yes	Yes	No	No	No	Yes

Решение :

Во [latex]II[/latex], [latex]III[/latex] и [latex]IV[/latex] координатных четвертях данная фигура удовлетворяет неравенству [latex]|x| + |y| \leq 5[/latex], а в [latex]IV[/latex] — неравенству [latex]x^2 + y^2 \leq 25[/latex]. Программа должна проверять, подходят ли числа [latex]x[/latex] и [latex]y[/latex] соответствующему неравенству (в зависимости от координатной четверти, в которой они находятся).

Код :

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

int main() 
{
	double x, y;
	cin >> x >> y;
	cout << (abs(x) + abs(y) <= 5 || x > 0 && y > 0 && x*x + y*y <= 25 ? "Yes" : "No");
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x, y;

cin >> x >> y;

cout << (abs(x) + abs(y) <= 5 || x > 0 && y > 0 && x*x + y*y <= 25 ? "Yes" : "No");

return 0;

}

Рабочая версия кода на Ideone.

Related Images:

Mif 17.20

02/10/2015 by Таран Таня

Задача. Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

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

Координаты точки в формате [latex](x, y)[/latex] ([latex]x, y[/latex] — действительные числа).

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

Вывести «YES», если точка принадлежит фигуре, и «NO» в противоположном случае.
(Точку, которая находится на контуре, также считаем принадлежащей данной фигуре).

Тесты

[latex]x[/latex]	[latex]y[/latex]	Результат
0	0	YES
-5	-5	YES
0	2.5	YES
3.5	4.2	YES
-4	-2.7	YES
3	-4	NO
-2	-1.5	NO
1	6	NO
3.5	0.5	NO
1000	2	NO

Решение

Проанализировав фигуру, можно определить, что она не симметрична, хотя данное свойство было бы нам полезно. Однако мы имеем полное право выполнить параллельный перенос фигуры на [latex]0.5[/latex] единиц влево. Рассмотрим текущее расположение фигуры.

Работать с фигурой стало проще, благодаря симметричности относительно начала координат [latex]O[/latex]. Для того чтобы не противоречить данному условию из-за выполненного сдвига, как только считываем координаты, уменьшаем абсциссу на [latex]0.5[/latex] единиц.
(На рисунке выделены основные данные, обозначенные определенными константами, которые понадобятся нам в ходе решения).

Для определения принадлежности точки фигуре будем постепенно убирать те области, в которых точка явно не может принадлежать фигуре:

В первую очередь исключим все точки, у которых модули значений координат превышают [latex]5.5[/latex] по оси абсцисс или [latex]5[/latex] по оси ординат.
(Условие проверки : [latex]|y| > c [/latex] [latex]\vee[/latex] [latex]|x| > d [/latex] )
Осталось рассмотреть две области, в которых точка не принадлежит фигуре тогда и только тогда, когда лежит ниже чем прямая [latex]y = 2[/latex] и правее [latex]x = 1.5[/latex] или же выше чем [latex]y = -2[/latex] и левее [latex]x =- 1.5[/latex].
(Условие проверки : [latex](x < -b[/latex] [latex]\wedge[/latex] [latex]y > -a)[/latex] [latex]\vee[/latex] [latex](x > b[/latex] [latex]\wedge[/latex] [latex]y < a)[/latex])
Если хотя бы одно из предыдущих условий выполнилось, приходим к заключению, что точка не принадлежит данной фигуре. Выводим «NO».
В противном случае выводим «YES».

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

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

const double a = 2;
const double b = 1.5;
const double c = 5;
const double d = 5.5;

int main(){
	double x, y;
	cin >> x >> y;
	x -= 0.5;
	cout << (fabs(y) > c || fabs(x) > d || (x < -b && y > -a) || (x > b && y < a) ? "NO" : "YES");
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

const double a = 2;

const double b = 1.5;

const double c = 5;

const double d = 5.5;

int main(){

double x, y;

cin >> x >> y;

x -= 0.5;

cout << (fabs(y) > c || fabs(x) > d || (x < -b && y > -a) || (x > b && y < a) ? "NO" : "YES");

return 0;

}

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

Related Images:

Ю2.15

01/10/2015 by Таран Таня

Задача. Общая точка

Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.

Замечание. Необходимо рассмотреть различные случаи взаимной ориентации отрезков: на одной прямой, на параллельных или пересекающихся прямых. Тестирование должно предусмотреть все такие ситуации.

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

Координаты концов двух отрезков [latex]AB, CD [/latex] в формате [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] ([latex]x_i, y_i[/latex] — действительные числа).

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

Расположение отрезков, а именно:

«Intersect at point [latex](x, y)[/latex]»
«Don’t intersect»
«Paralell»
«On the same line, but don’t intersect»
«Overlap» (Находятся на одной прямой и хотя бы одна из точек совпадает)

Тесты

Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]	Расположение отрезков
1 1 5 4 1 3 5 3	Intersect at point (3.66667, 3)
-7 2 -4 2 -6 3 -3 3	Paralell
1 2 3 2 2 2 6 2	Overlap
1 2 4 2 5 2 7 2	On the same line, but don’t intersect
1 2 4 4 2 1 5 3	Paralell
1 1 4 2 7 3 10 4	On the same line, but don’t intersect
1 1 5 3 5 3 7 4	Overlap
1 1 5 4 1 4 5 2	Intersect at point (3.4, 2.8)
1 1 2 4 3 2 6 4	Don’t intersect

Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]	Расположение отрезков
1 1 1 5 3 2 3 4	Paralell
1 2 4 5 2 2 2 5	Intersect at point (2, 3)
2 1 2 2 2 4 2 6	On the same line, but don’t intersect
2 1 2 5 1 2 4 2	Intersect at point (2, 2)
1 2 4 2 2 3 2 5	Don’t intersect

Алгоритм решения

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

areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
( Основная формула: [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
getMin — возвращает минимум двух чисел.
getMax — возвращает максимум двух чисел.
projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
( Основная формула: [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
( Основная формула: [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
getCos — функция, принимающая координаты двух векторов и возвращающая косинус угла между ними.
( Основная формула: [latex]\frac{x_1x_2 + y_1y_2}{\sqrt(x_1^2 + y_1^2) + \sqrt(x_2^2 + y_2^2)}[/latex] )

Перейдем к основной части программы. Сразу следует оговорить, что последующее решение будет базироваться на векторах и работе с уравнением прямой вида [latex] y = kx + b [/latex], поэтому для удобства отдельно заведем переменные для координат векторов соответствующих отрезкам и значений вычисленных коэффициентов и свободных членов уравнений прямых. Одной из главных проблем на пути решения стали отрезки располагающиеся на прямых вида [latex]x = a [/latex], ведь если обратится к пунктам 5, 6 можно заметить, что в таких случаях мы получим исключение из-за деления на ноль. Этим вызвано вынужденное разделение программы на два блока — где ни один из отрезков не располагается параллельно оси ординат и когда хотя бы один из них параллелен. Это удается достичь благодаря инициализации логических переменных, принимающих значение true, когда отрезок расположен на прямой [latex]x = a[/latex]. Также изначально подсчитываем значения переменных yIntercept1, yIntercept2, slope1, slope2 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

Теперь мы можем приступить к общему рассмотрению сложившейся ситуации, когда прямые параллельные оси ординат отсутствуют:

Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
[latex] \left\{\begin{matrix}
k_1x + b_1 = y & \\
k_2x + b_2 = y &
\end{matrix}\right.[/latex]
Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
б) Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
в) Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:

Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
б) Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
При условии, что только одна из прямых имеет вид [latex]x = a[/latex], рассмотрим следующие ситуации:
а)Только одна из прямых имеет вид [latex]x = a[/latex] и обе имеют коэффициент угла наклона равный [latex]0[/latex]. Перед нами две прямые вида: [latex] y = b[/latex] и [latex]x = a [/latex]. Выполняем смену между соответствующими координатами, чтобы не дублировать код для двух аналогичных ситуаций и рассматриваем только одну из них. Нетрудно заметить, что единственным решением является точка [latex](x_3/x_4, y_1/y_2)[/latex] . Используя метод getCos, выполняем уже описанную выше проверку на принадлежность точки отрезку. Если да — выводим сообщение : «Intersect at point [latex](x_3, y_1)[/latex]», в противном случае : «Don’t intersect».
б) Однако, ни одна из предыдущих проверок могла не выполниться, так как существует еще одно расположение отрезков на прямых [latex] y = kx + b [/latex] и [latex]x = a [/latex]. Выполняем аналогичную операцию по смене координат во избежание дублирования кода. Единственным решением данной системы может являться точка [latex](x3/x4 + yIntercept1, x3/x4)[/latex]. Повторяем операции аналогичные последним из пункта б). Выводим сообщение: «Intersect at point [latex](x3 + yIntercept1, x3)[/latex]» или «Don’t intersect».
(В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

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

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

bool areCollinear(double x1, double y1, double x2, double y2) {
	return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность
}

double getMin(double x1, double x2) {
	return x1 < x2 ? x1 : x2;
}

double getMax(double x1, double x2) {
	return x1 > x2 ? x1 : x2;
}

// Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций
bool projectionsIntersect(double x1, double x2, double x3, double x4) {
	return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));
}

// Вычисление коэффициента угла наклона уравнения прямой
double getSlope(double x1, double  y1, double x2, double y2) {
	return (y2 - y1) / (x2 - x1); 
}

// Вычисление свободного члена уравнения прямой
double getYIntercept(double x1, double  y1, double x2, double y2) {
	return (x2 * y1 - x1 * y2) / (x2 - x1);
}

// Нахождение косинуса угла между векторами
double getCos(double x1, double  y1, double x2, double y2) {
	return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));
}

int main() {
    double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки
	bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a 
	double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки
	double xIntersection, yIntersection; // Координаты точки пересечения, если она существует
	double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков 
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	double vx1 = x2 - x1;
	double vy1 = y2 - y1; // Вычислим координаты векторов,
	double vx2 = x4 - x3; // Задаваемых данными отрезками
	double vy2 = y4 - y3;
	slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a
	slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона
	vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a 
    vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true
	if (!f1 && !f2) {
		xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений 
		yIntersection = slope1 * xIntersection + yIntercept1;
		if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках 
	        cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")"; 
	    else if (yIntercept1 == yIntercept2) {
    		if (projectionsIntersect(x1, x2, x3, x4))
        		cout << "Overlap";
            else 
		        cout << "On the same line, but don't intersect";
        } 
        else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4))) 
            cout << "Paralell";
	    else 
	        cout << "Don't intersect";
	} // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a
	else {
	    if (slope1 == 0 && slope2 == 0 && f1 && f2) {
		    if (x1 == x4 &&  projectionsIntersect(y1, y2, y3, y4))
        	    cout << "Overlap";
            else if (x1 != x4)
        	    cout << "Paralell";
            else
                cout << "On the same line, but don't intersect";
	    } // Блок для двух прямых вида x = a
        else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {
        	if (f1) {
        		swap(x1, x3);
        		swap(x2, x4);
        		swap(y1, y3);
        		swap(y2, y4);
        		swap(yIntercept1, yIntercept2);	
        	}
        	yIntersection = y1;
        	xIntersection = x3;
        	if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) 
        		cout << "Intersect at a point ("  << xIntersection << "," << yIntersection << ")";
            else 
               	cout << "Don't intersect";
        } // Блок для прямых вида y = b и x = a
        else if (slope1 == 0 ^ slope2 == 0) {
        	if (slope1 == 0) {
        		swap(x1, x3);
        		swap(x2, x4);
        		swap(y1, y3);
        		swap(y2, y4);
        		swap(yIntercept1, yIntercept2);
        	}
        	xIntersection = x3;
        	yIntersection = x3 + yIntercept1;
        	if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) 
        		cout << "Intersect at a point ("  << xIntersection << "," << yIntersection << ")";
        	else 
        		cout << "Don't intersect";
        } // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b
    } // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a
	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <iostream>

#include <math.h>

using namespace std;

bool areCollinear(double x1, double y1, double x2, double y2) {

return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность

}

double getMin(double x1, double x2) {

return x1 < x2 ? x1 : x2;

}

double getMax(double x1, double x2) {

return x1 > x2 ? x1 : x2;

}

// Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций

bool projectionsIntersect(double x1, double x2, double x3, double x4) {

return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));

}

// Вычисление коэффициента угла наклона уравнения прямой

double getSlope(double x1, double y1, double x2, double y2) {

return (y2 - y1) / (x2 - x1);

}

// Вычисление свободного члена уравнения прямой

double getYIntercept(double x1, double y1, double x2, double y2) {

return (x2 * y1 - x1 * y2) / (x2 - x1);

}

// Нахождение косинуса угла между векторами

double getCos(double x1, double y1, double x2, double y2) {

return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));

}

int main() {

double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки

bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a

double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки

double xIntersection, yIntersection; // Координаты точки пересечения, если она существует

double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

double vx1 = x2 - x1;

double vy1 = y2 - y1; // Вычислим координаты векторов,

double vx2 = x4 - x3; // Задаваемых данными отрезками

double vy2 = y4 - y3;

slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a

slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона

vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a

vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true

if (!f1 && !f2) {

xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений

yIntersection = slope1 * xIntersection + yIntercept1;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else if (yIntercept1 == yIntercept2) {

if (projectionsIntersect(x1, x2, x3, x4))

cout << "Overlap";

else

cout << "On the same line, but don't intersect";

}

else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4)))

cout << "Paralell";

else

cout << "Don't intersect";

} // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a

else {

if (slope1 == 0 && slope2 == 0 && f1 && f2) {

if (x1 == x4 && projectionsIntersect(y1, y2, y3, y4))

cout << "Overlap";

else if (x1 != x4)

cout << "Paralell";

else

cout << "On the same line, but don't intersect";

} // Блок для двух прямых вида x = a

else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {

if (f1) {

swap(x1, x3);

swap(x2, x4);

swap(y1, y3);

swap(y2, y4);

swap(yIntercept1, yIntercept2);

}

yIntersection = y1;

xIntersection = x3;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else

cout << "Don't intersect";

} // Блок для прямых вида y = b и x = a

else if (slope1 == 0 ^ slope2 == 0) {

if (slope1 == 0) {

swap(x1, x3);

swap(x2, x4);

swap(y1, y3);

swap(y2, y4);

swap(yIntercept1, yIntercept2);

}

xIntersection = x3;

yIntersection = x3 + yIntercept1;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else

cout << "Don't intersect";

} // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b

} // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a

return 0;

}

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

Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)

Related Images:

Mif 17.2

30/09/2015 by Алина Гончарова

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

Решение

Данный рисунок находится в I и IV четверти, следовательно [latex] x [/latex] может быть только положительным, а [latex] y [/latex], как положительным, так и отрицательным. На рисунке нам даны две окружности. Одна с центром в точке (-0.5;0) и радиусом 3, а другая (0;0) и радиусом 5. Нам нужно, чтобы наша точка находилась только в первой и четвертой четвертях и при этом, чтоб выходила за пределы первой окружности, и чтоб не выходила за предел второй окружности. Для того, чтобы узнать принадлежит ли точка данной фигуре нужно подставить значения и проверить будут ли они принадлежать рисунку с помощью уравнений двух окружностей и описанных выше условий.

Уравнение окружности выглядит так: $\left(x-a \right)^2+\left(y-b \right)^2=R^2$ . Подставим значения центров окружностей и получим, что для первой окружности уравнение имеет вид:[latex](x+0.5)^{2}+y^{2}=3^{2}[/latex], а для второй: [latex] x^{2}+y^{2}=5^{2}[/latex].

Код

#include <iostream>
using namespace std;
 
const int r1 = 3;
const int r2 = 5;
 
int main() {
	double x, y;
	cin >> x >> y;
	cout << (x > 0 && ((x + 0.5) * (x + 0.5)  + y * y >= r1 * r1) && (x * x + y * y <= r2 * r2) ? "yes" : "no");
	return 0;
}

#include <iostream>

using namespace std;

const int r1 = 3;

const int r2 = 5;

int main() {

double x, y;

cin >> x >> y;

cout << (x > 0 && ((x + 0.5) * (x + 0.5) + y * y >= r1 * r1) && (x * x + y * y <= r2 * r2) ? "yes" : "no");

return 0;

}

Тесты

Входные данные	Выходные данные
4 5	no
1 2	no
2 -2	yes

Задача взята отсюда.
Код программы на Ideone.com.

Related Images:

e-olymp 918. Какая четверть?

14/09/2015 by Станислав Коциевский

Задача. Задана точка с координатами [latex]x[/latex] и [latex]y[/latex]. Определить, в какой координатной четверти она расположена.

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

В единственной строке через пробел заданы [latex]2[/latex] вещественных числа — координаты точки, значения координат по модулю не превышают [latex]100[/latex].

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex], если однозначно определить четверть невозможно.»

#include <iostream>
using namespace std;
int main ()
{
    double x;
    cin>>x;
    double y;
    cin>>y;
    cout<<((x==0)||(y==0)?"0":(x>0?
    (y>0?"1":"4"):(y>0?"2":"3")));
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

double x;

cin>>x;

double y;

cin>>y;

cout<<((x==0)||(y==0)?"0":(x>0?

(y>0?"1":"4"):(y>0?"2":"3")));

return 0;

}

Ссылка на код на ideone.
Ссылка на засчитанное решение.

Тесты

[latex]x[/latex]	[latex]y[/latex]	четверть	[latex]x[/latex]	[latex]y[/latex]	четверть
2	-2	4	0	54	0
5	7	1	-3	4	2
-3	0	0	-3	-8	3
0	0	0

Поскольку в любом случае мы обращаемся к оператору вывода, имеет смысл вложить условия в этот оператор. Сначала мы проверяем, не равна ли хотя бы одна переменная нулю. Если да — выводим [latex] 0[/latex], если нет — проверяем, больше ли [latex]x[/latex] нуля. Если да — это будет первая или четвертая четверть, если нет — вторая или третья. Внутри проверки [latex]x[/latex] проверяем [latex]y[/latex]. Если y больше нуля — это первая или вторая четверть, если меньше — вторая или третья.

Related Images:

А59д

05/11/2014 by Стеблинський Ігор Віталійович

Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Определить, принадлежит ли точка с координатами [latex]x[/latex], [latex]y[/latex] заштрихованной части плоскости.

Тесты:

KX	KY	ПРИНАДЛЕЖИТ?
1	1	нет
0	0	да
0.5	0	да
0.25	0.5	да
-0.25	1.5	нет

#include <iostream>
#include <math.h>
using namespace std;
double f (double x, double x0, double x1, double y, double y0, double y1)
{
	return  (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);
} 
int main() {
	double xa, ya, xb, yb, xc, yc, xd, yd,xk,yk;
	xa = -0.5; 
	ya = 0;
	xb = 0;
	yb = 1;
	xc = 0.5;
	yc = 0;
	xd = 0;
	yd = -1;
	cin >> xk >> yk;
	double l,m,q,w;
	l = f(xk,xa,xb,yk,ya,yb);
	m = f(xk,xb,xc,yk,yb,yc);
	q = f(xk,xc,xd,yk,yc,yd);
	w = f(xk,xd,xa,yk,yd,ya);
	if ((l >= 0) && (m >= 0)  && (q >= 0) && (w >= 0))
	{
		printf ("Принадлежит");
	}
	else
		printf ("Не принадлежит");
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double f (double x, double x0, double x1, double y, double y0, double y1)

{

return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);

}

int main() {

double xa, ya, xb, yb, xc, yc, xd, yd,xk,yk;

xa = -0.5;

ya = 0;

xb = 0;

yb = 1;

xc = 0.5;

yc = 0;

xd = 0;

yd = -1;

cin >> xk >> yk;

double l,m,q,w;

l = f(xk,xa,xb,yk,ya,yb);

m = f(xk,xb,xc,yk,yb,yc);

q = f(xk,xc,xd,yk,yc,yd);

w = f(xk,xd,xa,yk,yd,ya);

if ((l >= 0) && (m >= 0) && (q >= 0) && (w >= 0))

{

printf ("Принадлежит");

}

else

printf ("Не принадлежит");

return 0;

}

Ссылка на код: http://ideone.com/R3DlCS

import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static double f (double x, double x0, double x1, double y, double y0, double y1){
		return  (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);
	} 
	public static void main (String[] args) throws java.lang.Exception
	{
		double xa, ya, xb, yb, xc, yc, xd, yd,xk,yk;
		xa = -0.5; 
		ya = 0;
		xb = 0;
		yb = 1;
		xc = 0.5;
		yc = 0;
		xd = 0;
		yd = -1;
		Scanner in = new Scanner(System.in);
		xk = in.nextDouble();
		yk = in.nextDouble();
		double l,m,q,w;
		l = f(xk,xa,xb,yk,ya,yb);
		m = f(xk,xb,xc,yk,yb,yc);
		q = f(xk,xc,xd,yk,yc,yd);
		w = f(xk,xd,xa,yk,yd,ya);
		if ((l >= 0) && (m >= 0)  && (q >= 0) && (w >= 0)){
			System.out.printf("Принадлежит " ); 
		}
		else
			System.out.printf("Не принадлежит " ); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

static double f (double x, double x0, double x1, double y, double y0, double y1){

return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);

}

public static void main (String[] args) throws java.lang.Exception

{

double xa, ya, xb, yb, xc, yc, xd, yd,xk,yk;

xa = -0.5;

ya = 0;

xb = 0;

yb = 1;

xc = 0.5;

yc = 0;

xd = 0;

yd = -1;

Scanner in = new Scanner(System.in);

xk = in.nextDouble();

yk = in.nextDouble();

double l,m,q,w;

l = f(xk,xa,xb,yk,ya,yb);

m = f(xk,xb,xc,yk,yb,yc);

q = f(xk,xc,xd,yk,yc,yd);

w = f(xk,xd,xa,yk,yd,ya);

if ((l >= 0) && (m >= 0) && (q >= 0) && (w >= 0)){

System.out.printf("Принадлежит " );

}

else

System.out.printf("Не принадлежит " );

}

Ссылка на код: ссылка

Ход решения:

Зададим функцией [latex]f\left({x}\right)[/latex] уравнение прямой для двух точек с координатами[latex]\left(x_{0} ; y_{0}\right)[/latex] и [latex]\left(x_{1} ; y_{1}\right)[/latex], которое имеет вид: [latex]\left( x — x_{0}\right)\cdot\left( y_{1} — y_{0}\right) — \left( y-y_{0}\right)\cdot\left( x_{1} — x_{0}\right) = 0[/latex]

Подставим нужную нам точку в уравнение каждой прямой. Если значение положительное, то точка находится со внутренней стороны. На самом деле в двух четвертях значение будет отрицательное, но для удобства я сделал так, чтобы они были тоже положительны (отнимая вершины наоборот в тех четвертях, где значение отрицательное). То есть, если значение во всех 4 случаях будут положительные, либо [latex]= 0[/latex] (Значение [latex]0[/latex] означает что наша точка лежит на прямой, а следовательно принадлежит фигуре) мы можем утверждать что точка находится в заштрихованной плоскости. В противном случае она находится вне неё.

Related Images:

А59к

07/10/2014 by Недомовний Владислав

Задача.

Даны действительные числа [latex]x[/latex],[latex]y[/latex]. Определить, принадлежит ли точка с координатами [latex](x;y)[/latex] заштрихованной части плоскости.

Тесты.

Ввод	Вывод
[latex](-5.25;1.5)[/latex]	Принадлежит
[latex](-3;1)[/latex]	Принадлежит
[latex](0.6;0.6)[/latex]	Принадлежит
[latex](-0.8;0.9)[/latex]	Принадлежит
[latex](0.5;0.4)[/latex]	Не принадлежит
[latex](-0.25;-0.3)[/latex]	Не принадлежит

Код.

(C++)

#include <stdio.h>
#include <math.h>

int main()
{
 double x,y; //описание переменных для хранения входных данных
 scanf("%lf%lf",&x,&y); //ввод координат точки
 if((y>=1) || (x>=-1 && x<=1 && y>=fabs(x))) printf("Belongs"); //проверка
 else printf("Doesn't belong");
 return 0;
}

#include <stdio.h>

#include <math.h>

int main()

{

double x,y; //описание переменных для хранения входных данных

scanf("%lf%lf",&x,&y); //ввод координат точки

if((y>=1) || (x>=-1 && x<=1 && y>=fabs(x))) printf("Belongs"); //проверка

else printf("Doesn't belong");

return 0;

}

Java

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

class Ideone
{
	public static void main (String[] args) 
	{
		double x,y; //описание переменных для хранения входных данных
		Scanner sc = new Scanner(System.in);
		x = sc.nextDouble(); //ввод координат точки
		y = sc.nextDouble();
        if ((y >= 1) || (x >= -1 && x <= 1 && y >= Math.abs(x))) System.out.printf("Belongs"); //проверка
        else System.out.printf("Doesn't belong");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

double x,y; //описание переменных для хранения входных данных

Scanner sc = new Scanner(System.in);

x = sc.nextDouble(); //ввод координат точки

y = sc.nextDouble();

if ((y >= 1) || (x >= -1 && x <= 1 && y >= Math.abs(x))) System.out.printf("Belongs"); //проверка

else System.out.printf("Doesn't belong");

}

Решение.

Решение задачи сводится к поиску условия, при котором точка будет принадлежать данной части плоскости. В данной задаче условие будет такое: точка находиться выше прямой [latex]y=1[/latex], то есть ордината точки [latex]y\geq 1[/latex] (границы включаем) или точка находится выше графика функции [latex]y=\left|x \right|[/latex] на промежутке [latex]x[/latex]∈ [latex]\left[-1;1 \right][/latex], то есть [latex]y\geq \left|x \right|[/latex] , [latex]-1\leq x\leq 1[/latex] (границы включаем).

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

Related Images:

А52

03/10/2014 by Бровко Ілля

Задача. Даны действительный числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex], [latex]s[/latex], [latex]t[/latex], [latex]u[/latex]([latex]s[/latex] и [latex]t[/latex] одновременно не равны нулю). Известно, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] не лежат на прямой [latex]l[/latex], заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] принадлежат разным полуплоскостям.

В этой задаче надо воспользоваться тем, что две точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на прямой, определяемой уравнением [latex]sx + ty + u = 0[/latex], принадлежат одной полуплоскости, если [latex]sa + tb + u[/latex] и [latex]sc + td + u[/latex] – числа одного знака. Справедлив и более общий факт: если уравнение [latex]F(x, y) = 0[/latex] определяет прямую или кривую, разбивающую координатную плоскость на две части, то точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на этой линии, принадлежат одной и той же части плоскости, если [latex]F(a, b)[/latex] и [latex]F(c, d)[/latex]– числа одного знака.

a	b	c	d	s	t	u	Ответ
5	-4	2	9	6	-3	7	Обе точки принадлежат разным полуплоскостям.
-5	-4	-6	-3	2	7	-1	Обе точки принадлежат одной полуплоскости.
-5	-4	-6	-3	0	0	-1	Условие некорректно:s и t не должны одновременно равняются нулю.
4	7	2	1	-4	3	-5	Одна, либо обе из точек лежат на прямой, соответственно не принадлежат ни одной из полуплоскостей.

В программу вводятся исходные данные, среди которых координаты точек [latex](a, b)[/latex] и [latex](c, d)[/latex]. Если набор значений будет таким, что выполнится уравнение прямой [latex]sx+ty+u=0[/latex], (где x— a и d. А y— b и d), то это значит, что одни из точек (или сразу две) принадлежат прямой и следовательно не принадлежат ни одной из полуплоскостей. Если результаты уравнений [latex](s*a)+(t*b)+u[/latex] и [latex](s*c)+(t*d)+u[/latex]- числа одного знака, то точки лежат в одной полуплоскости. Если же эти числа разного знака, то обе точки принадлежат разным полуплоскостям.

Код на C++:

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

int main() 
{
	double a,b,c,d,s,t,u,R,K;
		scanf("%lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&s,&t,&u);
	if (s==0.00 && t==0.00)
	{
		printf ("Условие некорректно:s и t не должны одновременно равняются нулю. \n");
	}
	else
	{
		R=(s*a)+(t*b)+u;
		K=(s*c)+(t*d)+u;
		if (R==0.00 || K==0.00)
		{
			printf ("Одна, либо обе из точек лежат на прямой, соответственно не принадлежит ни одной из полуплоскостей. \n");
		}
		else if ((R>0.00 && K>0.00) || (R<0.00 && K<0.00))
		{
			printf ("Обе точки принадлежат одной полуплоскости. \n");
		}
		else
		{
			(R>0.00 && K<0.00) || (R<0.00 && K>0.00);
				printf ("Обе точки принадлежат разным полуплоскостям. \n");
		}
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

double a,b,c,d,s,t,u,R,K;

scanf("%lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&s,&t,&u);

if (s==0.00 && t==0.00)

{

printf ("Условие некорректно:s и t не должны одновременно равняются нулю. \n");

}

else

{

R=(s*a)+(t*b)+u;

K=(s*c)+(t*d)+u;

if (R==0.00 || K==0.00)

{

printf ("Одна, либо обе из точек лежат на прямой, соответственно не принадлежит ни одной из полуплоскостей. \n");

}

else if ((R>0.00 && K>0.00) || (R<0.00 && K<0.00))

{

printf ("Обе точки принадлежат одной полуплоскости. \n");

}

else

{

(R>0.00 && K<0.00) || (R<0.00 && K>0.00);

printf ("Обе точки принадлежат разным полуплоскостям. \n");

}

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Brovko
{
	public static void main (String[] args) throws java.lang.Exception
	{
	double a,b,c,d,s,t,u,R,K;
	Scanner in = new Scanner(System.in);
	a=in.nextDouble();
	b=in.nextDouble();
	c=in.nextDouble();
	d=in.nextDouble();
	s=in.nextDouble();
	t=in.nextDouble();
	u=in.nextDouble();
	if (s==0 && t==0)
	{
		System.out.printf("Условие некорректно:s и t не должны одновременно равняются нулю. \n");
	}
	else
	{
		R=(s*a)+(t*b)+u;
		K=(s*c)+(t*d)+u;
		if (R==0 || K==0)
		{
			System.out.printf ("Одна, либо обе из точек лежат на прямой, соответсвенно не пренадлежит ни одной из полуплоскостей. \n");
		}
		else if ((R>0 && K>0) || (R<0 && K<0))
		{
			System.out.printf ("Обе точки принадлежат одной полуплоскости. \n");
		}
		else
		{
			if((R>0 && K<0) || (R<0 && K>0));
			{
				System.out.printf ("Обе точки принадлежат разным полуплоскостям. \n");
			}
		}
	}
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Brovko

{

public static void main (String[] args) throws java.lang.Exception

{

double a,b,c,d,s,t,u,R,K;

Scanner in = new Scanner(System.in);

a=in.nextDouble();

b=in.nextDouble();

c=in.nextDouble();

d=in.nextDouble();

s=in.nextDouble();

t=in.nextDouble();

u=in.nextDouble();

if (s==0 && t==0)

{

System.out.printf("Условие некорректно:s и t не должны одновременно равняются нулю. \n");

}

else

{

R=(s*a)+(t*b)+u;

K=(s*c)+(t*d)+u;

if (R==0 || K==0)

{

System.out.printf ("Одна, либо обе из точек лежат на прямой, соответсвенно не пренадлежит ни одной из полуплоскостей. \n");

}

else if ((R>0 && K>0) || (R<0 && K<0))

{

System.out.printf ("Обе точки принадлежат одной полуплоскости. \n");

}

else

{

if((R>0 && K<0) || (R<0 && K>0));

{

System.out.printf ("Обе точки принадлежат разным полуплоскостям. \n");

}

С программой можно ознакомится тут (C++)/тут (Java).

Related Images:

Ю1.27

27/09/2014 by Сорокина Полина

Задача: Треугольник задаётся координатами своих вершин на плоскости: [latex]A\left(x_{1};y_{1} \right), B\left(x_{2};y_{2} \right), C\left(x_{3};y_{3} \right)[/latex] . Найти точку [latex]D[/latex], симметричную точке [latex]A[/latex] относительно стороны [latex]BC[/latex].

[latex]a_{x}[/latex]	[latex]a_{y}[/latex]	[latex]b_{x}[/latex]	[latex]b_{y}[/latex]	[latex]c_{x}[/latex]	[latex]c_{y}[/latex]	[latex]d_{x}[/latex]	[latex]d_{y}[/latex]
2	2	0	0	1	0	2	-2
-4	5	-2	3	-2	2	0	5
-3	-3	-4	-1	-1	-4	-2	-2
5	2	3.5	1	4.5	4	2.9	2.7

C++:

#include <stdio.h>
#include <math.h>

int main(void) {
	double ax, ay, bx, by, cx, cy, dx, dy;//Даны по условию или нужно найти.
	double A1, B1, C1, A2, B2, C2, ox, oy;//Используются для вычислений.
	printf("Введите координаты точек A, B, C.\n");
	scanf("%lf %lf %lf %lf %lf %lf\n", &ax, &ay, &bx, &by, &cx, &cy);
	A1=cy-by;//Постоянные из уравнения прямой BC.
	B1=bx-cx;
	C1=by*(cx-bx)-bx*(cy-by);
	A2=-B1;//Постоянные из уравнения прямой a.
	B2=A1;
	C2=B1*ax-A1*ay;
	ox=(B1*C2-B2*C1)/(A1*B2-A2*B1);//Координаты точки О.
	oy=(C1*A2-C2*A1)/(A1*B2-A2*B1);
	dx=2*ox-ax;//Координаты точки D.
	dy=2*oy-ay;
	printf("D(%lf;%lf)\n", dx, dy);
	return 0;
}

#include <stdio.h>

#include <math.h>

int main(void) {

double ax, ay, bx, by, cx, cy, dx, dy;//Даны по условию или нужно найти.

double A1, B1, C1, A2, B2, C2, ox, oy;//Используются для вычислений.

printf("Введите координаты точек A, B, C.\n");

scanf("%lf %lf %lf %lf %lf %lf\n", &ax, &ay, &bx, &by, &cx, &cy);

A1=cy-by;//Постоянные из уравнения прямой BC.

B1=bx-cx;

C1=by*(cx-bx)-bx*(cy-by);

A2=-B1;//Постоянные из уравнения прямой a.

B2=A1;

C2=B1*ax-A1*ay;

ox=(B1*C2-B2*C1)/(A1*B2-A2*B1);//Координаты точки О.

oy=(C1*A2-C2*A1)/(A1*B2-A2*B1);

dx=2*ox-ax;//Координаты точки D.

dy=2*oy-ay;

printf("D(%lf;%lf)\n", dx, dy);

return 0;

}

Java:

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		
		double ax, ay, bx, by, cx, cy, dx, dy;//Даны по условию или нужно найти.
		double A1, B1, C1, A2, B2, C2, ox, oy;//Используются для вычислений.
		
		System.out.println("Введите координаты точек A, B, C.");
		ax = in.nextDouble();
		ay = in.nextDouble();
		bx = in.nextDouble();
		by = in.nextDouble();
		cx = in.nextDouble();
		cy = in.nextDouble();
		
		A1=cy-by;//Постоянные из уравнения прямой BC.
		B1=bx-cx;
		C1=by*(cx-bx)-bx*(cy-by);
		A2=-B1;//Постоянные из уравнения прямой a.
		B2=A1;
		C2=B1*ax-A1*ay;
		ox=(B1*C2-B2*C1)/(A1*B2-A2*B1);//Координаты точки О.
		oy=(C1*A2-C2*A1)/(A1*B2-A2*B1);
		dx=2*ox-ax;//Координаты точки D.
		dy=2*oy-ay;
		System.out.println("D("+dx+";"+dy+")");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double ax, ay, bx, by, cx, cy, dx, dy;//Даны по условию или нужно найти.

double A1, B1, C1, A2, B2, C2, ox, oy;//Используются для вычислений.

System.out.println("Введите координаты точек A, B, C.");

ax = in.nextDouble();

ay = in.nextDouble();

bx = in.nextDouble();

by = in.nextDouble();

cx = in.nextDouble();

cy = in.nextDouble();

A1=cy-by;//Постоянные из уравнения прямой BC.

B1=bx-cx;

C1=by*(cx-bx)-bx*(cy-by);

A2=-B1;//Постоянные из уравнения прямой a.

B2=A1;

C2=B1*ax-A1*ay;

ox=(B1*C2-B2*C1)/(A1*B2-A2*B1);//Координаты точки О.

oy=(C1*A2-C2*A1)/(A1*B2-A2*B1);

dx=2*ox-ax;//Координаты точки D.

dy=2*oy-ay;

System.out.println("D("+dx+";"+dy+")");

}

Для всех переменных ([latex]a_{x}[/latex], [latex]a_{y}[/latex], [latex]b_{x}[/latex], [latex]b_{y}[/latex], [latex]c_{x}[/latex], [latex]c_{y}[/latex] — координаты точек [latex]A, B, C[/latex], даны по условию; [latex]d_{x}[/latex], [latex]d_{y}[/latex] — координаты точки [latex]D[/latex] — нужно найти) я использовала тип double, так как они могут быть вещественными числами.

Найдём уравнение прямой [latex]BC[/latex] по формуле [latex]\frac{\left(x-x_{1} \right)}{\left(x_{2}-x_{1} \right)}=\frac{\left(y-y_{1} \right)}{\left(y_{2}-y_{1} \right)}[/latex]. Подставляем значения: [latex]\frac{\left(x-b_{x} \right)}{\left(c_{x}-b_{x} \right)}=\frac{\left(y-b_{y} \right)}{\left(c_{y}-b_{y} \right)}[/latex]. Приводим к виду: [latex]x\left(c_{y}-b_{y} \right)-y\left(c_{x}-b_{x} \right)+b_{y}\left(c_{x}-b_{x} \right)-b_{x}\left(c_{y}-b_{y} \right)=0[/latex].
Переменными [latex]A_{1}[/latex], [latex]B_{1}[/latex], [latex]C_{1}[/latex] я обозначила постоянные при [latex]x, y[/latex] и свободный член, чтобы уравнение приняло вид: [latex]A_{1}\cdot x+B_{1}\cdot y+C_{1}=0[/latex].

Проведём прямую через точку [latex]A[/latex] перпендикулярно прямой [latex]BC[/latex]. Составим её уравнение по формуле: [latex]A\left(y-a_{y} \right)-B\left(x-a_{x} \right)=0[/latex]. Получим: [latex]A_{1}\cdot y-B_{1}\cdot x+B_{1}\cdot a_{x}-A_{1}\cdot a_{x}=0[/latex]. Аналогично для постоянных в этом уравнении я использовала переменные [latex]A_{2}[/latex], [latex]B_{2}[/latex], [latex]C_{2}[/latex]. Соответственно, [latex]A_{2}=-B_{1}[/latex], [latex]B_{2}=A_{1}[/latex], [latex]C_{2}=B_{1}\cdot a_{x}-A_{1}\cdot a_{y}[/latex].

Теперь найдём точку пересечения этой прямой и прямой [latex]BC[/latex] — точку [latex]O\left(o_{x};o_{y} \right)[/latex]. Получим: [latex]o_{x}=\frac{B_{1}\cdot C_{2}-B_{2}\cdot C_{1}}{A_{1}\cdot B_{2}-A_{2}\cdot B_{1}}[/latex] и [latex]o_{y}=\frac{C_{1}\cdot A_{2}-C_{2}\cdot A_{1}}{A_{1}\cdot B_{2}-A_{2}\cdot B_{1}}[/latex].

Так как точка [latex]D[/latex] симметрична точке [latex]A[/latex] относительно [latex]BC[/latex], и [latex]AD[/latex] пересекается с [latex]BC[/latex] в точке [latex]O[/latex]: точка [latex]O[/latex] — середина [latex]AD[/latex]. Из формулы координаты середины отрезка ( [latex]o_{x}=\frac{a_{x}+d_{x}}{2}[/latex] и [latex]o_{y}=\frac{a_{y}+d_{y}}{2}[/latex] ) находим [latex]d_{x}=2\cdot o_{x}-a_{x}[/latex] и [latex]d_{y}=2\cdot o_{y}-a_{y}[/latex].

Задача на Ideone:
C++
Java

Related Images:

А60б

23/09/2014 by Марченко Філіп Олександрович

Задача: Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть [latex]u[/latex] определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом ( запись [latex](x, y)\epsilon D[/latex] означает, что точка с координатами [latex]x[/latex], [latex]y[/latex] принадлежит [latex]D[/latex]):

[latex]u=\left\{\begin{matrix}-3, \text{if} (x, y)\epsilon D\\ y^{2} \end{matrix}\right.[/latex]

Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Определить [latex]u[/latex].

Код на С++:

#include <iostream>
using namespace std;

int main() {
	double x, y;  
	scanf (" %lf%lf ", &x, &y); // чтение из стандартного потока ввода.
	if (( x*x + y*y <= 1) && (y<=x/2)) {	//утверждение
		printf ("u=-3");		//истина
	}
	else {
		printf ("u = %2.2lf", y*y); 	//ложь
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y;

scanf (" %lf%lf ", &x, &y); // чтение из стандартного потока ввода.

if (( x*x + y*y <= 1) && (y<=x/2)) { //утверждение

printf ("u=-3"); //истина

}

else {

printf ("u = %2.2lf", y*y); //ложь

}

return 0;

}

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат [latex]u[/latex]
[latex]0[/latex]	[latex]0[/latex]	[latex]-3[/latex]
[latex]0[/latex]	[latex]1[/latex]	[latex]1. 00[/latex]
[latex]1[/latex]	[latex]0[/latex]	[latex]-3[/latex]
[latex]-1[/latex]	[latex]0[/latex]	[latex]0. 00[/latex]
[latex]0[/latex]	[latex]-1[/latex]	[latex]-3[/latex]
[latex]0,6[/latex]	[latex]0,8[/latex]	[latex]0. 64[/latex]
[latex]0,5[/latex]	[latex]-0,5[/latex]	[latex]-3[/latex]

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class circle {
	public static void main (String [] args){
		Scanner sc = new Scanner (System.in);
		double x, y;
		x = sc.nextDouble();
		y = sc.nextDouble();
		System.out.println ((( x*x + y*y <= 1) && (y <= x/2))? ("u = -3"):("u = " + y*y));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class circle {

public static void main (String [] args){

Scanner sc = new Scanner (System.in);

double x, y;

x = sc.nextDouble();

y = sc.nextDouble();

System.out.println ((( x*x + y*y <= 1) && (y <= x/2))? ("u = -3"):("u = " + y*y));

}

Для того, чтобы определить находится ли нужная точка с координатами [latex](x,y)[/latex] в заштрихованной части графика, нужно задать такое условие, чтобы эта точка находилась в круге [latex]x^{2}+y^{2}=1[/latex] и была ниже прямой [latex]y=\frac{x}{2}[/latex].

Отсюда следует, что если [latex]x^{2}+y^{2}\leqslant1[/latex] и [latex]y\leqslant\frac{x}{2}[/latex], то точка принадлежит заштрихованной части круга.

Результат [latex]u[/latex] выводится с точностью до двух знаков после запятой.

Запустить код и проверить тесты можно тут: http://ideone.com/N3UoQ7.

Related Images:

А59е

19/09/2014 by Сорокина Полина

Задача А59е. Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Определить, принадлежит ли точка [latex]x[/latex], [latex]y[/latex] заштрихованной части плоскости.

Значение [latex]x[/latex]	Значение [latex]y[/latex]	Комментарий
0	0	Принадлежит фигуре.
-2	0	Принадлежит фигуре.
0	1	Принадлежит фигуре.
1	0	Принадлежит фигуре.
0	-1	Принадлежит фигуре.
-2	1	Не принадлежит фигуре.
-2	-0.5	Принадлежит фигуре.
1	-1	Не принадлежит фигуре.
0.5	0.5	Принадлежит фигуре.

С++:

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

struct point { 
	double x, y; 
};

struct point get() {
	struct point a;
	cin >> a.x >> a.y;
	return a;
}

double dotline(struct point a, struct point b, struct point d) {
	return (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x);
}
 
bool dotdot(struct point a, struct point b, struct point c, struct point d) {
	return dotline(a, b, c) * dotline(a, b, d) >= 0;
}
 
int main() {
	struct point a, b, c;
	a.x = -2; a.y = 0; b.x = 0; b.y = 1; c.x = 0; c.y = -1;
	struct point d = get();
	if(d.x<0){
		if(dotdot(a,b,c,d) && dotdot(b,c,a,d) && dotdot(c,a,b,d)){
			cout << "Точка D принадлежит заштрихованной части плоскости.";
		} else {
			cout << "Точка D не принадлежит заштрихованной части плоскости.";
		}
	} else {
		if (sqrt(pow(d.x, 2) + pow(d.y, 2))<=1) {
			cout << "Точка D принадлежит заштрихованной части плоскости.";
		}
		else {
			cout << "Точка D не принадлежит заштрихованной части плоскости.";
		}
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

struct point {

double x, y;

};

struct point get() {

struct point a;

cin >> a.x >> a.y;

return a;

}

double dotline(struct point a, struct point b, struct point d) {

return (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x);

}

bool dotdot(struct point a, struct point b, struct point c, struct point d) {

return dotline(a, b, c) * dotline(a, b, d) >= 0;

}

int main() {

struct point a, b, c;

a.x = -2; a.y = 0; b.x = 0; b.y = 1; c.x = 0; c.y = -1;

struct point d = get();

if(d.x<0){

if(dotdot(a,b,c,d) && dotdot(b,c,a,d) && dotdot(c,a,b,d)){

cout << "Точка D принадлежит заштрихованной части плоскости.";

} else {

cout << "Точка D не принадлежит заштрихованной части плоскости.";

}

} else {

if (sqrt(pow(d.x, 2) + pow(d.y, 2))<=1) {

cout << "Точка D принадлежит заштрихованной части плоскости.";

}

else {

cout << "Точка D не принадлежит заштрихованной части плоскости.";

}

return 0;

}

Java:

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

class Ideone
{
	public static class Point {
		private double x, y;
		public Point(double x, double y){
			this.x = x;
			this.y = y;
		}
		public double getX(){
			return this.x;
		}
		public double getY(){
			return this.y;
		}
		private static double dotLine(Point a, Point b, Point d) {
			return (d.getX() - a.getX()) * (b.getY() - a.getY()) - (d.getY() - a.getY()) * (b.getX() - a.getX());
		}
		public static boolean dotDot(Point a, Point b, Point c, Point d) {
			return dotLine(a, b, c) * dotLine(a, b, d) >= 0;
		}
	}
	
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		Point a = new Point(-2, 0);
		Point b = new Point(0, 1);
		Point c = new Point(0, -1);
		Point d = new Point(in.nextDouble(), in.nextDouble());
		if(d.getX()<0){
			if(Point.dotDot(a,b,c,d) && Point.dotDot(b,c,a,d) && Point.dotDot(c,a,b,d)){
				System.out.println("Точка D принадлежит заштрихованной части плоскости.");
			} else {
				System.out.println("Точка D не принадлежит заштрихованной части плоскости.");
			}
		} else {
			if (Math.sqrt(Math.pow(d.getX(), 2) + Math.pow(d.getY(), 2))<=1) {
				System.out.println("Точка D принадлежит заштрихованной части плоскости.");
			}
			else {
				System.out.println("Точка D не принадлежит заштрихованной части плоскости.");
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static class Point {

private double x, y;

public Point(double x, double y){

this.x = x;

this.y = y;

}

public double getX(){

return this.x;

}

public double getY(){

return this.y;

}

private static double dotLine(Point a, Point b, Point d) {

return (d.getX() - a.getX()) * (b.getY() - a.getY()) - (d.getY() - a.getY()) * (b.getX() - a.getX());

}

public static boolean dotDot(Point a, Point b, Point c, Point d) {

return dotLine(a, b, c) * dotLine(a, b, d) >= 0;

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

Point a = new Point(-2, 0);

Point b = new Point(0, 1);

Point c = new Point(0, -1);

Point d = new Point(in.nextDouble(), in.nextDouble());

if(d.getX()<0){

if(Point.dotDot(a,b,c,d) && Point.dotDot(b,c,a,d) && Point.dotDot(c,a,b,d)){

System.out.println("Точка D принадлежит заштрихованной части плоскости.");

} else {

System.out.println("Точка D не принадлежит заштрихованной части плоскости.");

}

} else {

if (Math.sqrt(Math.pow(d.getX(), 2) + Math.pow(d.getY(), 2))<=1) {

System.out.println("Точка D принадлежит заштрихованной части плоскости.");

}

else {

System.out.println("Точка D не принадлежит заштрихованной части плоскости.");

}

Если точка [latex]D[/latex] лежит справа от оси [latex]OY[/latex], ищем расстояние от неё до точки [latex]O\left(0,0 \right)[/latex]. Если оно меньше либо равно [latex]1[/latex], точка [latex]D[/latex] принадлежит полукругу.

Если точка [latex]D[/latex] лежит слева от оси [latex]OY[/latex], будем проводить прямые через каждые две вершины треугольника [latex]ABC[/latex], где [latex]A\left(-2,0 \right)[/latex], [latex]B\left(0,1 \right)[/latex], [latex]C\left(1,0 \right)[/latex].

Воспользуемся уравнением прямой:
[latex]\left ( x-x_{A} \right )\left ( y_{B}-y_{A} \right )-\left ( y-y_{A} \right )\left ( x_{B}-x_{A} \right )=0[/latex]

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

Функция dotLine определяет положение точки относительно прямой: она вычисляет значение в уравнении прямой и определяет, к какой части плоскости относится точка.

Для того, чтобы точка [latex]D[/latex] принадлежала треугольнику, она должна с каждой вершиной треугольника находиться по одну сторону от прямой, проходящей через две другие вершины.

Функция dotDot определяет, расположены ли точки в одной части плоскости.

Если уравнение прямой даст 0, то точка [latex]D[/latex] лежит на прямой и принадлежит треугольнику.

Задача на Ideone:
C++
Java