Mif 15

26/10/2015 by Женя Максимова

Задача. Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырехмерном пространстве.

Тесты

(1)

№	[latex]A_0[/latex]	[latex]A_1 [/latex]	[latex]A_2[/latex]	[latex]A_3[/latex]	[latex]B_0[/latex]	[latex]B_1[/latex]	[latex]B_2[/latex]	[latex]B_3[/latex]
1	1	0	0	0	2	0	0	0
2	1	0	0	0	3	0	0	0
3	-1	1	0	6	-2	-1	1	6
4	1	1	1	1	2	2	2	2
5	1	1	1	2	8	5	7	10
6	1	1	0	0	1	0	1	1
7	3	4	7	8	9	5	6	2
8	1	2	2	3	1	4	8	9

(2)

№	[latex]C_0[/latex]	[latex]C_1[/latex]	[latex]C_2[/latex]	[latex]C_3[/latex]	[latex]D_0[/latex]	[latex]D_1[/latex]	[latex]D_2[/latex]	[latex]D_3[/latex]	[latex]r[/latex]
1	1	1	0	0	2	1	0	0	1.000000
2	2	4	0	0	2	4	3	0	4.000000
3	-1	-1	0	6	2	1	1	6	1.154701
4	-9	-9	-9	-9	-5	-5	-5	-5	12.000000
5	8	0	0	0	2	1	1	1	1.414214
6	2	3	2	0	1	4	9	1	3.000000
7	7	4	11	15	15	5	12	9	9.000000
8	5	7	2	23	4	8	8	21	13.000000

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

#include "stdio.h"
#include <cmath>

double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];

double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
    {
        double r = 0;
        //calculation of three vectors
        //u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
        diff(P1, P0, u);  diff(Q1, Q0, v);  diff(Q0, P0, w0);
        //calculation of supporting scalar variables
        //a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
        double  a, b, c, d, e;
        a = dot(u,u);  // a=u^2;
        b = dot(u,v);         
        c = dot(v,v);  // c=v^2;
        d = dot(u,w0);
        e = dot(v,w0);
        //calculation of main determinant
        // D = b^2 - a*c
        double D = b*b - a*c;
        if (D == 0) //lines are parallel
            {
                double t0=-e/c; 
                double t1=-e/c; 
                double s0 = (-e+b)/c ; 
                double s1= (e-c)*b/(c*a);
                if (in(t0) || in(t1) || in(s0) || in(s1))
                    {
                        double wq[4];
                        prod(e/c,v,  wq);  //projection w0 on line q
                        double wd[4];
                         diff(w0,wq,  wd);
                          r = abs(wd);
                           return r ; //r = |w0 - wq|
                    }
                //else minimal distance between segments equals minimal distance between ends of segments
                        r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
                         return r;   
            }
        // else lines are not parallel
            {
                //calculation of determinants
                double D1 = b*e - c*d,  D2 = a*e - b*d;
                //calculation of parameters for minimal segment between lines
                double sc = D1/D, tc = D2/D;
                if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
                    {
                        return r = sd(sc,tc); // r = |wc|
                    }
                //else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
                    {
                        double t1 = 0,   s1=_(d/a);
                        double t2 = _(-2*e/c), s2=0;
                        double t3 = 1,   s3=_(2*(b+d)/a);
                        double t4 = _(2*(b+e)/c), s4=0;
                         return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4)); 
                    }
            }
    }

int main()
    {
        scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
        scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
        scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
        scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
         printf("%lf\n", InterSegmentDistance4d());
          return 0;
    }

double dot(double * u, double * v)//scalar production of two vectors
    {
        return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
    }

double abs(double * u)//length of vector
    {
        return sqrt(dot(u,u));
    }

double min(double a, double b, double c, double d)//minimal from four values
    {
        double m = a;
        if(m>b) m = b;
         if(m>c) m = c;
          if(m>d) m = d;
           return m;
    }

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)
    {
        c[0]=a[0]-b[0];
        c[1]=a[1]-b[1];
        c[2]=a[2]-b[2];
        c[3]=a[3]-b[3];
    }

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)
    {
        c[0]=a[0]+b[0];
        c[1]=a[1]+b[1];
        c[2]=a[2]+b[2];
        c[3]=a[3]+b[3];
    }

void prod(double k, double * u, double * v)//production of number and vector
    {
        v[0] = k * u[0];
        v[1] = k * u[1];
        v[2] = k * u[2];
        v[3] = k * u[3];
    }

bool in(double s)//checking if the vatue is in [0,1]
    {
        return 0 <= s && s <= 1 ;
    }

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]
    {
        return  in(t) && in(s);
    }

double sd(double s, double t)//distance between two points defined by two parameters s and t
    {
        double Pc[4], Qc[4], W[4];
        prod(s,u, Pc);
        prod(t,v, Qc);
         summ(Pc,P0, Pc);
         summ(Qc,Q0, Qc);
          diff(Qc, Pc, W);
           return  abs(W);
    }

double _(double s)//restrict a value s on the interval [0,1]
    {
        double s1 = s;
        if(s > 1)s1 = 1;
        if(s < 0)s1 = 0;
         return s1;
    }

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include "stdio.h"

#include <cmath>

double dot(double * u, double * v);

double abs(double * u);

double min(double a, double b, double c, double d);

void prod(double k, double * u, double * v);

void diff(double * a, double * b, double * c);

void summ(double * a, double * b, double * c);

bool in(double s);

bool in(double s, double t);

double sd(double s, double t);

double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];

double u[4],v[4],w0[4];

double InterSegmentDistance4d()

//input: four 4d points P0, P1, Q0, Q1

// output: r = minimal distance between lines segments P0P1 and Q0Q1

{

double r = 0;

//calculation of three vectors

//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0

diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);

//calculation of supporting scalar variables

//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v

double a, b, c, d, e;

a = dot(u,u); // a=u^2;

b = dot(u,v);

c = dot(v,v); // c=v^2;

d = dot(u,w0);

e = dot(v,w0);

//calculation of main determinant

// D = b^2 - a*c

double D = b*b - a*c;

if (D == 0) //lines are parallel

{

double t0=-e/c;

double t1=-e/c;

double s0 = (-e+b)/c ;

double s1= (e-c)*b/(c*a);

if (in(t0) || in(t1) || in(s0) || in(s1))

{

double wq[4];

prod(e/c,v, wq); //projection w0 on line q

double wd[4];

diff(w0,wq, wd);

r = abs(wd);

return r ; //r = |w0 - wq|

}

//else minimal distance between segments equals minimal distance between ends of segments

r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));

return r;

}

// else lines are not parallel

{

//calculation of determinants

double D1 = b*e - c*d, D2 = a*e - b*d;

//calculation of parameters for minimal segment between lines

double sc = D1/D, tc = D2/D;

if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines

{

return r = sd(sc,tc); // r = |wc|

}

//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]

{

double t1 = 0, s1=_(d/a);

double t2 = _(-2*e/c), s2=0;

double t3 = 1, s3=_(2*(b+d)/a);

double t4 = _(2*(b+e)/c), s4=0;

return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));

}

int main()

{

scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);

scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);

scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);

scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);

printf("%lf\n", InterSegmentDistance4d());

return 0;

}

double dot(double * u, double * v)//scalar production of two vectors

{

return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];

}

double abs(double * u)//length of vector

{

return sqrt(dot(u,u));

}

double min(double a, double b, double c, double d)//minimal from four values

{

double m = a;

if(m>b) m = b;

if(m>c) m = c;

if(m>d) m = d;

return m;

}

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)

{

c[0]=a[0]-b[0];

c[1]=a[1]-b[1];

c[2]=a[2]-b[2];

c[3]=a[3]-b[3];

}

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)

{

c[0]=a[0]+b[0];

c[1]=a[1]+b[1];

c[2]=a[2]+b[2];

c[3]=a[3]+b[3];

}

void prod(double k, double * u, double * v)//production of number and vector

{

v[0] = k * u[0];

v[1] = k * u[1];

v[2] = k * u[2];

v[3] = k * u[3];

}

bool in(double s)//checking if the vatue is in [0,1]

{

return 0 <= s && s <= 1 ;

}

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]

{

return in(t) && in(s);

}

double sd(double s, double t)//distance between two points defined by two parameters s and t

{

double Pc[4], Qc[4], W[4];

prod(s,u, Pc);

prod(t,v, Qc);

summ(Pc,P0, Pc);

summ(Qc,Q0, Qc);

diff(Qc, Pc, W);

return abs(W);

}

double _(double s)//restrict a value s on the interval [0,1]

{

double s1 = s;

if(s > 1)s1 = 1;

if(s < 0)s1 = 0;

return s1;

}

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

Отрезки лежат на параллельных прямых или на одной прямой.
Отрезки лежат на пересекающихся либо на скрещивающихся прямых.

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

По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а [latex]s[/latex] и [latex]t[/latex] — параметры. При [latex]s=0[/latex] или [latex] t=0[/latex] мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex] или [latex]t=1[/latex] — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex] соединяет 2 ближайшие точки [latex]Q_c[/latex] и [latex]P_c[/latex] при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex] \begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex] \begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы: [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex] \begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex] Если [latex]D \neq 0[/latex], то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем [latex]D = 0[/latex], легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

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

Найдем проекцию точки [latex]P_0[/latex] на линию [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора [latex]\vec w_0[/latex] на линию [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке [latex]Q_0[/latex], а начало в новой точке [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки [latex]P_0[/latex] и [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием: [latex]r = \left| P_0 P_{0q} \right|[/latex].

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex] \begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка [latex]P_{0q}[/latex] лежит на прямой [latex]q[/latex], задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex] отрезку [latex]Q_0 Q_1[/latex] можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex] [latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex] [latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex] [latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex] и [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров [latex](s_c, \; t_c)[/latex] принадлежит области: [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров [latex]s_c \not\in \left[0,1\right][/latex] или [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области: [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex] (см. рисунок ниже):

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум [latex]w^2[/latex] достигается в точке [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex] \begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

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

Related Images:

Mif 17.8

10/10/2015 by Катя Писова

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

Решение:

Фигура, изображенная на рисунке, ограничена двумя дугами окружностей с центрами в начале координат. Для того, чтобы точка принадлежала ей необходимо, чтобы ее ордината была больше либо равнялась двум, а также, чтобы выполнялись такие неравенства: [latex]{x}^{2}+{y}^{2}>=16[/latex] и [latex]{x}^{2}+{y}^{2}<=36[/latex], где [latex]16[/latex] и [latex]36[/latex] — радиусы двух окружностей, возведенные в квадрат по формуле.

Код:

#include <iostream>
using namespace std;
 
int main() {
    double x,y;
    cin>>x>>y;
    cout<<( y >= 2 && x*x + y*y >= 16 && x*x + y*y <= 36 ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin>>x>>y;

cout<<( y >= 2 && x*x + y*y >= 16 && x*x + y*y <= 36 ? "YES" : "NO");

return 0;

}

Тесты:

x	y	Результат
0	0	NO
-1	4	YES
6	-2	NO
2.5	3	NO

Тут можно посмотреть решение задачи на ideone.com

Related Images:

Mif 17.13

07/10/2015 by Таня Корнилова

Задача №17.13

Условие

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

Тесты

Входные данные (точка K)	Выходные данные
(3;4)	no
(1;1)	yes
(1;4)	yes
(3;0)	yes
(0;6)	no
(-13; -3)	no
(-4.5; -3)	yes

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

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

struct point { double x, y; };

double g(struct point a, struct point b, struct point k){
	return (k.x - a.x) * (b.y - a.y) - (k.y - a.y) * (b.x - a.x);
} // определяем местоположение точки K относительно прямой АВ

bool f(struct point a, struct point b, struct point c, struct point k){
	return g(a, b, c) * g(a, b, k) >= 0;
} // определяем, лежит ли точка С в одной полуплоскости с точкой К

int main() {
	struct point a { 1, 4 }, b { 5, -4 }, c { -5, -3 };
	double x, y;
	struct point k { k.x, k.y };
	cin >> k.x >> k.y;
	cout << ((f(a,b,c,k) && f(b,c,a,k) && f(c,a,b,k)) ? "yes" : "no");
	return 0;

}

#include <iostream>

#include <stdio.h>

using namespace std;

struct point { double x, y; };

double g(struct point a, struct point b, struct point k){

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

} // определяем местоположение точки K относительно прямой АВ

bool f(struct point a, struct point b, struct point c, struct point k){

return g(a, b, c) * g(a, b, k) >= 0;

} // определяем, лежит ли точка С в одной полуплоскости с точкой К

int main() {

struct point a { 1, 4 }, b { 5, -4 }, c { -5, -3 };

double x, y;

struct point k { k.x, k.y };

cin >> k.x >> k.y;

cout << ((f(a,b,c,k) && f(b,c,a,k) && f(c,a,b,k)) ? "yes" : "no");

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

Related Images:

Mif 8

07/10/2015 by Настя Ивасенко

Задача

Условие взято отсюда

Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.

Тесты

[latex]a_1[/latex] [latex]a_2[/latex]	[latex]b_1[/latex] [latex]b_2[/latex]	[latex]c_1[/latex][latex]c_2[/latex]	[latex]d_1[/latex] [latex]d_2[/latex]	Ответ
0 0	1 0	1 1	0 1	квадрат
0 -3	2 0	0 3	-2 0	ромб
0 0	4 0	4 1	1 4	прямоугольник
0 0	10 0	12 4	2 4	пaраллелограмм
0 0	2 0	1 1	0 1	трапеция
0 0	0 2	1 1	1 0	трапеция
-4 -5	-15 7	5 8	6 -7	произвольный
0 0	1 0	10 20	-5 7	произвольный

Код

#include <iostream>
using namespace std;
 
int main() {
	int a1, a2, b1, b2, c1, c2, d1, d2;
	double  AB, BC, CD, DA, AC, BD, A, B, C, D;
	cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;
	AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени
	BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));
	CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));
	DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));
	AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени
	BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));
	if(AB==CD && BC==DA) {
		if (AB==BC){
			if(AC==BD){
				cout << "квадрат";
			}
			else {
				cout << "ромб";
			}
		}
		else 
		if (AC==BD){
			cout<< "прямоугольник";
		}
		else{
			cout << "параллелограмм";
		}
	}
	else 
	if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){
		cout << "трапеция";
	}
	else {
		cout << "произвольный";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a1, a2, b1, b2, c1, c2, d1, d2;

double AB, BC, CD, DA, AC, BD, A, B, C, D;

cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;

AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени

BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));

CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));

DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));

AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени

BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));

if(AB==CD && BC==DA) {

if (AB==BC){

if(AC==BD){

cout << "квадрат";

}

else {

cout << "ромб";

}

else

if (AC==BD){

cout<< "прямоугольник";

}

else{

cout << "параллелограмм";

}

else

if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){

cout << "трапеция";

}

else {

cout << "произвольный";

}

return 0;

}

Решение

Для начала стоит найти длины всех сторон:

[latex]AB^{2}=((a1-b1)^{2}+(a2-b2)^{2})[/latex]. (аналогично для остальных сторон)

Затем можно найти длины диагоналей четырёхугольника

[latex]AC^{2}=((a1-c1)^{2}+(a2-c2)^{2})[/latex]. (аналогично для [latex]BD[/latex]).

Через условие задаем равность противоположных сторон [latex]AB=CD[/latex] и [latex]BC=DA[/latex]:

У ромба смежные стороны равны, но если у ромба диагонали равны, то это квадрат;
Если четырёхугольник не является квадратом, но диагонали равны, то это прямоугольник;
В противном случае — параллелограмм.

Если одна из пар противополижных сторон параллельны, то данный четырёхугольник — трапеция. Впротивном случае — произвольный четырёхугольник.

Код на ideone

Related Images:

e-olymp 60. Площадь многоугольника

06/10/2015 by Кудымовская Вика

Задача. Площадь многоугольника

Условие задачи

Заданы координаты [latex]n[/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex]n[/latex]. В следующих [latex]n[/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex]x_i, y_i[/latex]. Известно, что [latex]3 \leq n \leq 1000, -1000 \leq x[i], y[i] \leq 1000[/latex].

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

Площадь многоугольника [latex]S[/latex], вычисленная с точностью до трех десятичных знаков.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные ([latex]n[/latex], [latex]x_i, y_i[/latex])	Выходные данные
1.	3, (0, 0), (0, 2), (2, 0)	2.000
2.	4, (-1000, 500), (-500, 1000), (2, 10), (35, 60)	339865.000
3.	10, (51, -20), (15, 3), (45, 200), (100, -100), (201, 55), (70, -80), (25, 333), (999, 0), (500, 77), (5, -6)	124562.500
4.	5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2)	1446.000

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() { 
    int n, x1, x2, y1, y2, x, y; 
    double sum=0; 
    cin >> n >> x >> y; 
    x1=x; 
    y1=y; 
    for (int i=0; i<(n-1); i++) { 
        cin >> x2 >> y2; 
        sum=sum+(x1+x2)*(y2-y1); 
        x1=x2; 
        y1=y2; 
    } 
    sum=sum+(x+x2)*(y-y2); 
    cout << fixed << setprecision(3) << abs(sum) / 2 << endl;
    return 0; 
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n, x1, x2, y1, y2, x, y;

double sum=0;

cin >> n >> x >> y;

x1=x;

y1=y;

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

cin >> x2 >> y2;

sum=sum+(x1+x2)*(y2-y1);

x1=x2;

y1=y2;

}

sum=sum+(x+x2)*(y-y2);

cout << fixed << setprecision(3) << abs(sum) / 2 << endl;

return 0;

}

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

Даны координаты последовательных [latex]n[/latex] вершин многоугольника: [latex]x_i, y_i[/latex]. Для того, чтобы вычислить его площадь, воспользуемся формулой: [latex]S=\frac{1}{2}\cdot |\sum_{i=1}^{n}{(x_i + x_{i+1})\cdot (y_i — y_{i+1})}|[/latex], где [latex]x_0, y_0=x_{n+1}, y_{n+1}[/latex].

Подробнее о вычислении площади произвольного многоугольника можно прочесть здесь.

Для запроса на выполнение перейдите по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Related Images:

Mif 17.4

04/10/2015 by Настя Ивасенко

Условие задачи (17.4)

Условие

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

Тесты

x	y	Ответ
4	3	yes
1	4	yes
2	2	no
6	2	no
-1	0	no

Решение

Точки, которые принадлежат ромбу, находятся между линиями, которые создают этот ромб.

Можно заметить, что эти сумма координат этих точек находится в сегменте между [latex]5[/latex] и [latex]11[/latex]:

[latex]5\leq x+y\leq 11[/latex];

Их разность в сегменте от [latex]-3[/latex] до [latex]3[/latex]:

[latex]-3\leq x-y\leq 3[/latex];

Если сумма или разность данных координат больше или меньше заданых чисел, то точка не принадлежит ромбу.

Код

#include <iostream>
using namespace std;
 
int main() {
    double x, y;
    cin >> x >> y;
    if ((x+y>=5 && x+y<=11 && x-y>=-3 && x-y<=3)) {
        cout <<"yes";
    }
    else
    {
        cout << "no";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y;

cin >> x >> y;

if ((x+y>=5 && x+y<=11 && x-y>=-3 && x-y<=3)) {

cout <<"yes";

}

else

{

cout << "no";

}

return 0;

}

Код на IDEONE

Related Images:

Mif 17.15

01/10/2015 by Кудымовская Вика

Задача Mif17.15

Условие задачи

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

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

В одной строке задано два числа – координаты точки latex[/latex].

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

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	1.5 7	Не принадлежит
2.	3 4	Не принадлежит
3.	2 -3.6	Принадлежит
4.	5 0	Принадлежит
5.	0 1	Не принадлежит
6.	0 -4	Не принадлежит
7.	3 3	Принадлежит
8.	2 3	Принадлежит

Реализация

#include <iostream>
using namespace std;
 
int main () {
    double x, y, k, m, n;
    int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника
    cin >> x >> y; //координаты произвольной точки
    k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);
    m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);
    n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);
    cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main () {

double x, y, k, m, n;

int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника

cin >> x >> y; //координаты произвольной точки

k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);

m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);

n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);

cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");

return 0;

}

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

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex] или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

Mif 17.10

01/10/2015 by Кондратюк Настя

Задача

Принадлежит ли точка [latex]\left( x;y \right)[/latex] фигуре на рисунке?

Тесты

	[latex]\left( x;y \right)[/latex]	Ответ
1.	(1;6)	нет
2.	(-5;3)	нет
3.	(0;0)	нет
4.	(3.5;1.7)	да
5.	(2;4)	да

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

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

int main() {
	double x,y;
	cin >> x >> y;
	if (x>=0 && y>=0 && ((x*x+y*y)<=36) && (y>=(3-x))){
		cout << "YES";
	}
    else cout << "NO";

	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

if (x>=0 && y>=0 && ((x*x+y*y)<=36) && (y>=(3-x))){

cout << "YES";

}

else cout << "NO";

return 0;

}

ideone.com

Решение

Рисунок находится в I четверти, следовательно только точка с положительными [latex]x[/latex] и [latex]y[/latex] может принадлежать этому рисунку. Далее необходимо воспользоваться уравнением окружности [latex]\left(x-a \right)^2+\left(y-b \right)^2=R^2[/latex], т.к. центр окружности(сегмент которой изображен на рисунке) находится в начале координат формула имеет такой вид: [latex]x^2+y^2=R^2[/latex]. Также рисунок ограничен прямой [latex]y=3-x[/latex]. Если [latex]x>0[/latex] и [latex]y>0[/latex] , [latex]R\leq6[/latex] , [latex]y\geq3-x[/latex], то точка принадлежит фигуре на рисунке.

Related Images:

Mif 17.5

30/09/2015 by Антон Локтев

Условие

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

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

Координаты точки [latex]\left(x,y\right)[/latex] на плоскости.

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

Если точка принадлежит фигуре, вывести «Принадлежит» (без кавычек), в противном случае — «Не принадлежит».

Задача взята отсюда.

Тесты

№	x	y	Вывод
1	1	-1	Принадлежит
2	0	0	Принадлежит
3	0	4	Принадлежит
4	5	0	Принадлежит
5	0	4.00001	Не принадлежит
6	-3	5	Не принадлежит
7	2	3	Принадлежит

Решение

Фигура в задаче представлена в виде двух четвертей окружностей, лежащих в I и IV четвертях с радиусами [latex] R1 [/latex] и [latex] R2 [/latex] , которые равны соответственно [latex] 4 [/latex] и [latex] 5 [/latex]. Центры окружностей находятся в начале координатных осей. Сразу после ввода координат точки выполняем проверку принадлежности фигуре, а именно: координата [latex]X\ge0[/latex] ? В случае отрицательного ответа программа выведет сообщение «Не принадлежит». Одновременно со знаком [latex]X[/latex] выполняется проверка с помощью формулы, полученной из уравнения окружности: [latex]{\left(x-{X}_{c}\right)}^{2}+{\left(y-{Y}_{c}\right)}^{2}\le{R}^{2}[/latex], где [latex]X_{c}[/latex] и [latex]Y_{c}[/latex] — координаты центра окружности. Если координаты точки проходят данную проверку для соответствующего радиуса, который зависит от знака [latex]Y[/latex], то точка принадлежит фигуре, в противном случае выведется сообщение «Не принадлежит».

Код

#include <iostream>
using namespace std;

int main(){
	double y,Yc,x,Xc,R1,R2;
	Xc = 0; // координаты центров окружностей
	Yc = 0;
	R1 = 4; 
	R2 = 5;
	cin >> x >> y; 
	cout << ((x >= 0 && ((y > 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R1*R1) ||
			            (y <= 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R2*R2)))? "Принадлежит" : "Не принадлежит");
	return 0;
}

#include <iostream>

using namespace std;

int main(){

double y,Yc,x,Xc,R1,R2;

Xc = 0; // координаты центров окружностей

Yc = 0;

R1 = 4;

R2 = 5;

cin >> x >> y;

cout << ((x >= 0 && ((y > 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R1*R1) ||

(y <= 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R2*R2)))? "Принадлежит" : "Не принадлежит");

return 0;

}

Код на сайте ideone.com находится здесь.

Related Images:

Mif 17.6

30/09/2015 by Александр Димитриев

Условие

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

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

В одной строке задано два числа — координаты точки [latex](x;y)[/latex].

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

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

Тесты

Входные данные	Выходные данные
-3.5 2.5	NO
-1.5 2.5	YES
-2 5	YES
5 5	NO
-3 -1	NO
1 4	YES
3.3 4.4	YES
1.6 -3	NO
-4 2.2	NO

Код

#include <iostream>
using namespace std;

int main() {
	double x,y;
	cin >> x >> y;
	cout << (((x>=-2)&&(x<=3)&&(y>=2)&&(y<=5))||((x>3)&&(x<=5)&&(y>=2)&&(y<=3)) ? "YES": "NO");
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

cout << (((x>=-2)&&(x<=3)&&(y>=2)&&(y<=5))||((x>3)&&(x<=5)&&(y>=2)&&(y<=3)) ? "YES": "NO");

return 0;

}

Решение

В данной задаче я разбил фигуру на два прямоугольника и проверяю входят ли абсцисса и ордината данной точки в промежутки [latex]x=[-2;3]; y=[2;5][/latex](для большого прямоугольника) и [latex]x=(3;5]; y=[2;3][/latex](для маленького прямоугольника), если точка входит, то значит она принадлежит. В противном случае — нет.
Код программы

Related Images:

Ю2.6

30/09/2015 by Кудымовская Вика

Условие

Четырёхугольник [latex]ABCD[/latex] задан координатами своих вершин на плоскости: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex] и [latex]C(x_c,y_c)[/latex], [latex]D(x_d,y_d)[/latex]. Определить тип четырёхугольника: прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Учесть погрешность вычислений.

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

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

В одной строке заданы 8 чисел [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] — координаты вершин четырёхугольника [latex]ABCD[/latex], значения которых не превышают по модулю [latex]50[/latex].

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

В первой строке вывести: «Тип четырёхугольника: «(без кавычек).
Во второй строке вывести: «Произвольный четырёхугольник» или «Прямоугольник» или «Параллелограмм» или «Трапеция»(без кавычек). Одно исключает другое.

Также условие задачи можно посмотреть, скачав ознакомительную версию задачника А.Юркина здесь.

Тестирование

№	Координаты [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex]	Вердикт (тип четырёхугольника)
1.	-5 -4 -1 -2 -4 3 -1 -8	Параллелограмм
2.	-2 -3 7 3 -2 1 7 1	Трапеция
3.	0 0 1 1 0 1 1 0	Прямоугольник
4.	50 -20 3 -50 7 6 2 3	Произвольный четырёхугольник
5.	2 -3 -6 -1 4 7 6 3	Параллелограмм
6.	1 -5 6 20 2 0 13 -9	Произвольный четырёхугольник
7.	0 1 2 1 0 1 1 0	Параллелограмм
8.	-6 0 6 0 1 5 -4 -8	Прямоугольник

Реализация

#include <iostream>
#include <cmath>
using namespace std;
 
int main () {
    setlocale(LC_ALL,"Russian");
    int xa, xb, xc, xd, ya, yb, yc, yd; 
    cout << "Тип четырёхугольника: " << endl;
    cin >> xa >> xb >> xc >> xd >> ya >> yb >> yc >> yd;
    //диагонали AC и BD четырёхугольника ABCD обозначим, как l и m, они являются векторами
    long double l= abs(sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc -ya)));
    long double m= abs(sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd -yb)));
    if (((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)) || ((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya))) { 
        if (((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya)) && ((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb))) 
            if (l==m)
                cout << "Прямоугольник" << endl;
            else {
                cout << "Параллелограмм" << endl;
            }
        else {
            cout << "Трапеция" << endl;
        }
    }
    else {
        cout << "Произвольный четырехугольник" << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main () {

setlocale(LC_ALL,"Russian");

int xa, xb, xc, xd, ya, yb, yc, yd;

cout << "Тип четырёхугольника: " << endl;

cin >> xa >> xb >> xc >> xd >> ya >> yb >> yc >> yd;

//диагонали AC и BD четырёхугольника ABCD обозначим, как l и m, они являются векторами

long double l= abs(sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc -ya)));

long double m= abs(sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd -yb)));

if (((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)) || ((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya))) {

if (((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya)) && ((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)))

if (l==m)

cout << "Прямоугольник" << endl;

else {

cout << "Параллелограмм" << endl;

}

else {

cout << "Трапеция" << endl;

}

else {

cout << "Произвольный четырехугольник" << endl;

}

return 0;

}

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

Задан четырёхугольник [latex]ABCD[/latex] с такими координатами вершин: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex], [latex]C(x_c,y_c)[/latex] и [latex]D(x_d,y_d)[/latex]. В данной задаче будет уместным использование аппарата векторной алгебры. Пусть стороны четырёхугольника — векторы.
Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}[/latex], если [latex]a_i, b_i\ne0[/latex]. Координаты векторов [latex]\vec{b}[/latex] и [latex]\vec{d}[/latex] должны быть пропорциональны, что означает, что соответствующие стороны параллельны. Следовательно, [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Или же координаты векторов [latex]\vec{a}[/latex] и [latex]\vec{c}[/latex] должны быть пропорциональны. Проверяем: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex] и [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
Частным случаем параллелограмма является прямоугольник. Диагонали [latex] AC, BD[/latex] обозначим как [latex] l, m[/latex] соответственно. Пусть [latex] l, m[/latex] — векторы. Вычислим длины векторов [latex]\vec{l}[/latex], [latex]\vec{m}[/latex], пользуясь формулой. Получаем: [latex]\vec{|l|}= \sqrt{(x_c — x_a)\cdot (x_c -x_a) + (y_c — y_a)\cdot (y_c -y_a)}[/latex], [latex]\vec{|m|}= \sqrt{(x_d — x_b)\cdot (x_d -x_b) + (y_d — y_b)\cdot (y_d -y_b)}[/latex]. При условии, что [latex]\vec{l}=\vec{m}[/latex], имеем прямоугольник.

Более детально со свойствами и видами четырёхугольников можно ознакомиться здесь, а с основными сведениями из векторной алгебры — здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

Mif17.11

30/09/2015 by Андрей Яроцкий

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

Тесты:

№	Ввод [latex](x,y)[/latex]	Вывод
1	3 1	YES
2	-3 1	NO
3	-3 -1	NO
4	3 -1	YES
5	4 7	NO
6	4 -7	NO

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

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

int main() {
   double x, y, l; // x,y - координаты точки; l - расстояние от центра круга до точки
   double x1 = 0, y1 = 0, r = 6; // x1,y1 - центр круга; r - радиус
   double xz = 2; // начало сегмента круга
   cin >> x >> y;
   l = (x-x1)*(x-x1)+(y-y1)*(y-y1);
   if(x >= xz && r*r >= l) cout << "YES"; // область допустимых значений x
   else cout << "NO";
   return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x, y, l; // x,y - координаты точки; l - расстояние от центра круга до точки

double x1 = 0, y1 = 0, r = 6; // x1,y1 - центр круга; r - радиус

double xz = 2; // начало сегмента круга

cin >> x >> y;

l = (x-x1)*(x-x1)+(y-y1)*(y-y1);

if(x >= xz && r*r >= l) cout << "YES"; // область допустимых значений x

else cout << "NO";

return 0;

}

Решение:

Изучив рисунок, находим координаты трех точек сегмента круга. После, находим координаты центра круга и его радиус с помощью данного сайта. Если проекция точки на ось [latex]OX[/latex] не находиться в области допустимых значений [latex]x[/latex], то точка не принадлежит сегменту круга в любом случае. Если же первое условие выполняется, то точка принадлежит сегменту круга тогда, когда квадрат расстояния ([latex]l[/latex]) от центра круга до точки меньше либо равно квадрату радиуса ([latex]r[/latex]) круга ([latex]r*r[/latex] >= [latex]l[/latex])

Условие задачи здесь.

Ссылка на решение задачи на компиляторе ideone.com здесь.

Related Images:

Mif 17.19

30/09/2015 by Павел Загинайло

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

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Вывод
-3	0	no
-1.5	2	yes
2	5	yes
3	4	yes
3	3	no

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

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

#include <iostream>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

cout << ((((x>=-4)&&(x<=-1)&&(y>=1)&&(y<=7))||((x>=-1)&&(x<=3)&&(y>=4)&&(y<=7))) ? "yes" : "no");

return 0;

}

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

В данной программе проверяются допустимые значения [latex]x[/latex] и [latex]y[/latex], при которых точка с данными координатами может принадлежать данной фигуре. Если координаты соблюдают все условия, то программа выводит «yes», т.е. принадлежит . В остальных случаях на экран выводится «no».

Related Images:

ML18

28/09/2015 by Кудымовская Вика

Задача ML18

Условие задачи

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex], значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex])	Выходные данные
1	2 2 5 1 0 -1 3 5 10	16.0261556346
2	1 4 5 3 6 0 10.5 -2 -1	31.9047289894
3	15 26 13 32 18 56 80 0 -6.2	212.0962807371
4	-13 68 44 99 -100 70 0 2 1	450.5748518262
5	100 9 17 18 29 88 65 -16 0.36	310.4318979186

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main ()
{
	double x1, x2, x3, y1, y2, y3, z1, z2, z3;
	long double a, b, c, p;
	//стороны AB, BC, AC треугольника ABC обозначим 
	//соответственно, используя переменные a, b, c
	//используем значения переменных с плавающей точкой
	cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;
	a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));
	b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));
	c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));
	p= a + b + c;
	//вычисляем периметр 
	cout << fixed << setprecision(10) << p << endl;
	//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main ()

{

double x1, x2, x3, y1, y2, y3, z1, z2, z3;

long double a, b, c, p;

//стороны AB, BC, AC треугольника ABC обозначим

//соответственно, используя переменные a, b, c

//используем значения переменных с плавающей точкой

cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;

a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));

b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));

c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));

p= a + b + c;

//вычисляем периметр

cout << fixed << setprecision(10) << p << endl;

//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой

return 0;

}

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

Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

Ю2.3

26/12/2014 by Сіренко Валерія Сергіївна

Задача: Треугольник задан координатами своих вершин на плоскости: [latex]A(x_{a}, y_{a})[/latex], [latex]B(x_{b}, y_{b})[/latex], [latex]C(x_{c}, y_{c})[/latex]. Определить, является он прямо-, остро-, или тупоугольным.

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

Тесты:

[latex]x_{A}[/latex]	[latex]y_{A}[/latex]	[latex]x_{B}[/latex]	[latex]y_{B}[/latex]	[latex]x_{C}[/latex]	[latex]y_{C}[/latex]	Результат	комментарий
0	1	0	2	0	3	тупоугольный	пройден
1	4	3	2	6	2	тупоугольный	пройден
6	2	6	2	6	4	прямоугольный	пройден
2	1	2	3	5	3	прямоугольный	пройден
5	5	5	5	5	5	невозможно определить тип треугольника	пройден
2	1	3	4	4	1	остроугольный	пройден
2	1	1	3	4	4	остроугольный	пройден

Ссылка на С++ : http://ideone.com/LfWkbB

Ссылка на Java: http://ideone.com/yrS444

Код:

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    double xA, yA, xB, yB, xC, yC, AB, BC, CA, alpha, beta, gamma;
    cin >> xA >> yA >> xB >> yB >> xC >> yC;
    if ((xA==xB) && (xB==xC) && (yA == yB) && (yB == yC))
    {
        cout << ("Невозможно определить тип треугольника");
    }
    else if ((xA==xB && yA==yB) || (xB==xC && yB==yC) || (xC==xA && yC==yA))
    {
        cout << ("прямоугольный");    
    }
    else 
    {
        AB = sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));
        BC = sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));
        CA = sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));
        alpha = (AB*AB + CA*CA - BC*BC)/(2*AB*CA);
        beta = (AB*AB + BC*BC -CA*CA)/(2*AB*BC);
        gamma = (CA*CA + BC*BC - AB*AB)/(2*CA*BC);
        {
            if (( alpha == 0 ) || (beta == 0) || (gamma == 0))
            {
                cout << ("прямоугольный") ;
            }
            if ((alpha < 0)||(beta < 0) || (gamma < 0)) 
            {
                cout << ("тупоугольный") ;
            }
            if ((alpha > 0) && (beta > 0) && (gamma > 0))
            {
                cout << ("остроугольный") ;
            }
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double xA, yA, xB, yB, xC, yC, AB, BC, CA, alpha, beta, gamma;

cin >> xA >> yA >> xB >> yB >> xC >> yC;

if ((xA==xB) && (xB==xC) && (yA == yB) && (yB == yC))

{

cout << ("Невозможно определить тип треугольника");

}

else if ((xA==xB && yA==yB) || (xB==xC && yB==yC) || (xC==xA && yC==yA))

{

cout << ("прямоугольный");

}

else

{

AB = sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));

BC = sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));

CA = sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));

alpha = (AB*AB + CA*CA - BC*BC)/(2*AB*CA);

beta = (AB*AB + BC*BC -CA*CA)/(2*AB*BC);

gamma = (CA*CA + BC*BC - AB*AB)/(2*CA*BC);

{

if (( alpha == 0 ) || (beta == 0) || (gamma == 0))

{

cout << ("прямоугольный") ;

}

if ((alpha < 0)||(beta < 0) || (gamma < 0))

{

cout << ("тупоугольный") ;

}

if ((alpha > 0) && (beta > 0) && (gamma > 0))

{

cout << ("остроугольный") ;

}

return 0;

}

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        double xA, yA, xB, yB, xC, yC, AB, BC, CA, alpha, beta, gamma;
            Scanner in = new Scanner(System.in);
            xA = in.nextDouble();
            yA = in.nextDouble();
            xB = in.nextDouble();
            yB = in.nextDouble();
            xC = in.nextDouble();
            yC = in.nextDouble();
        if ((xA==xB) && (xB==xC) && (yA == yB) && (yB == yC))
        {
            System.out.printf ("Невозможно определить тип треугольника");
        }
        else if ((xA==xB && yA==yB) || (xB==xC && yB==yC) || (xC==xA && yC==yA))
        {
            System.out.printf ("прямоугольный");    
        }
        else 
        {
            AB = Math.sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));
            BC = Math.sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));
            CA = Math.sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));
            alpha = (AB*AB + CA*CA - BC*BC)/(2*AB*CA);
            beta = (AB*AB + BC*BC -CA*CA)/(2*AB*BC);
            gamma = (CA*CA + BC*BC - AB*AB)/(2*CA*BC);
            {
                if (( alpha == 0 ) || (beta == 0) || (gamma == 0))
                {
                    System.out.printf ("прямоугольный") ;
                }
                if ((alpha < 0)||(beta < 0) || (gamma < 0)) 
                {
                    System.out.printf ("тупоугольный") ;
                }
                if ((alpha > 0) && (beta > 0) && (gamma > 0))
                {
                    System.out.printf ("остроугольный") ;
                }
            }
        }
    }   
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

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

{

double xA, yA, xB, yB, xC, yC, AB, BC, CA, alpha, beta, gamma;

Scanner in = new Scanner(System.in);

xA = in.nextDouble();

yA = in.nextDouble();

xB = in.nextDouble();

yB = in.nextDouble();

xC = in.nextDouble();

yC = in.nextDouble();

if ((xA==xB) && (xB==xC) && (yA == yB) && (yB == yC))

{

System.out.printf ("Невозможно определить тип треугольника");

}

else if ((xA==xB && yA==yB) || (xB==xC && yB==yC) || (xC==xA && yC==yA))

{

System.out.printf ("прямоугольный");

}

else

{

AB = Math.sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));

BC = Math.sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));

CA = Math.sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));

alpha = (AB*AB + CA*CA - BC*BC)/(2*AB*CA);

beta = (AB*AB + BC*BC -CA*CA)/(2*AB*BC);

gamma = (CA*CA + BC*BC - AB*AB)/(2*CA*BC);

{

if (( alpha == 0 ) || (beta == 0) || (gamma == 0))

{

System.out.printf ("прямоугольный") ;

}

if ((alpha < 0)||(beta < 0) || (gamma < 0))

{

System.out.printf ("тупоугольный") ;

}

if ((alpha > 0) && (beta > 0) && (gamma > 0))

{

System.out.printf ("остроугольный") ;

}

Решение :

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

        if ((xA==xB) && (xB==xC) && (yA == yB) && (yB == yC))
    {
        cout << ("Невозможно определить тип треугольника");
    }
    else if ((xA==xB && yA==yB) || (xB==xC && yB==yC) || (xC==xA && yC==yA))
    {
        cout << ("прямоугольный");

if ((xA==xB) && (xB==xC) && (yA == yB) && (yB == yC))

{

cout << ("Невозможно определить тип треугольника");

}

else if ((xA==xB && yA==yB) || (xB==xC && yB==yC) || (xC==xA && yC==yA))

{

cout << ("прямоугольный");

Если не одно из этих условий не выполняется, то мы ищем стороны треугольника и по теореме косинусов находим косинус угла. Далее выполняем три таких условия, при которых определяется какой треугольник : остро- тупо- или прямоугольный

                        if (( alpha == 0 ) || (beta == 0) || (gamma == 0))
            {
                cout << ("прямоугольный") ;
            }
            if ((alpha < 0)||(beta < 0) || (gamma < 0)) 
            {
                cout << ("тупоугольный") ;
            }
            if ((alpha > 0) && (beta > 0) && (gamma > 0))
            {
                cout << ("остроугольный") ;
            }

if (( alpha == 0 ) || (beta == 0) || (gamma == 0))

{

cout << ("прямоугольный") ;

}

if ((alpha < 0)||(beta < 0) || (gamma < 0))

{

cout << ("тупоугольный") ;

}

if ((alpha > 0) && (beta > 0) && (gamma > 0))

{

cout << ("остроугольный") ;

}

Related Images:

А59и

12/11/2014 by Носуленко Марк

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

Вычислил уравнения прямых по формуле :

[latex]\frac{x-x_{a}}{x_{b}-x_{a}}=\frac{y-y_{a}}{y_{a}-y_{b}}[/latex]

Получил уравнения :

[latex]y=2x+3[/latex], [latex]y=-x[/latex], [latex]y=\frac{x-1}{3}[/latex]

Плоскость разделил на верхнюю и нижнюю части осью ox([latex]y\geq 0[/latex], [latex]y\leq 0[/latex]), при помощи первых двух уравнений выделил заштрихованную область в верхней части, при помощи первого и третьего соответственно в нижней(изменив знак «=» на «≥» или «≤»(в зависимости от того где должна лежать точка для выполнения условия) ).

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат:
-2	-1	Точка входит в заштрихованную область.
-2	-1.001	Точка не входит в заштрихованную область.
-2	-0.999	Точка не входит в заштрихованную область.
-1	1	Точка входит в заштрихованную область.
-1.001	1	Точка не входит в заштрихованную область.
-1	1.001	Точка не входит в заштрихованную область.
-1	0.999	Точка входит в заштрихованную область.
1	0	Точка входит в заштрихованную область.
1	-0.001	Точка не входит в заштрихованную область.

Сам код:

using namespace std;

int main() {
	double x, y;
	cin >> x >> y;
	if(y>=0 && y<=-x && x>=(y-3)/2 || y<=0 && x>=(y-3)/2 && y>=(x-1)/3)
		cout << "Точка входит в заштрихованную область.";
	else
		cout << "Точка не входит в заштрихованную область.";
	return 0;
}

using namespace std;

int main() {

double x, y;

cin >> x >> y;

if(y>=0 && y<=-x && x>=(y-3)/2 || y<=0 && x>=(y-3)/2 && y>=(x-1)/3)

cout << "Точка входит в заштрихованную область.";

else

cout << "Точка не входит в заштрихованную область.";

return 0;

}

Ссылка на код

Related Images:

А60е

07/11/2014 by Кібакова Надія Олександрівна

Задача

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

[latex]u=\left\{\begin{matrix}x+y,&\left(x,y\right)\in D\\x-y,&\left(x,y\right)\notin D\end{matrix}\right.[/latex]

Код C++

 #include <iostream>
 #include <math.h>
 using namespace std;
     
 int main() {
    double x, y;
    scanf("%lf %lf", &x, &y);
    double u = (y>=x*x) && (y<=exp(-x)) && (y<=exp(x))? x+y : x-y;
    printf("%7.3lf", u);
 return 0;
 }

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x, y;

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

double u = (y>=x*x) && (y<=exp(-x)) && (y<=exp(x))? x+y : x-y;

printf("%7.3lf", u);

return 0;

}

Код C++ на Ideone: www.ideone.com/s6vMul

Код Java

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

class Coordinates{
    public static void main (String[] args) throws java.lang.Exception {
        Scanner read = new Scanner(System.in);
        double x = read.nextDouble();
        double y = read.nextDouble();
        double u; 
        if((y >= x*x) && (y <= Math.exp(-x)) && (y <= Math.exp(x)))
            u = x+y;
        else 
            u = x-y;
        System.out.print(u);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Coordinates{

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

Scanner read = new Scanner(System.in);

double x = read.nextDouble();

double y = read.nextDouble();

double u;

if((y >= x*x) && (y <= Math.exp(-x)) && (y <= Math.exp(x)))

u = x+y;

else

u = x-y;

System.out.print(u);

}

Код Java на Ideone: A60e

Комментарии

Для всех трех функций необходимо проверить чтобы заданная ордината была больше [latex]y=x^{2}[/latex] и одновременно меньше [latex]y=e^{-x}[/latex] , [latex]y=e^{x}[/latex].

Тесты

x	y	Результат	Комментарий
0	0	0	Пройден
0	1	1	Пройден
34	45	-11	Пройден

Related Images:

А60д

30/10/2014 by Ковальський Олександр Дмитрович

Задача.

Пусть D — заштрихованная часть плоскости и пусть u определяется по x и y следующим образом :

[latex]u=\begin{cases} \sqrt{|x^{2}-1|} & \text{ if } (x, y)\epsilon D \\ x+y & \end{cases}[/latex]

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

Тесты.

Ввод		Вывод
x	y	u
0	0	1
0	0.5	1
-0.3	0.6	0.953939
0.3	0.6	0.953939
-0.2	-0.1	-0.3
0.8	0.6	1.4
0.5	-0.5	0

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

int main() 
	{
		double x,y;
		cin>>x>>y;
		cout<< (((x*x+y*y<=1)&&(y>=fabs(x))) ? sqrt(abs(x*x-1)):x+y) <<endl;
		return 0;
	}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x,y;

cin>>x>>y;

cout<< (((x*x+y*y<=1)&&(y>=fabs(x))) ? sqrt(abs(x*x-1)):x+y) <<endl;

return 0;

}

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        double x = in.nextDouble(),y = in.nextDouble();
		System.out.println(((x * x + y * y <= 1) && (y >= Math.abs(x))) ? Math.sqrt(Math.abs(x * x - 1)) : x + y);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double x = in.nextDouble(),y = in.nextDouble();

System.out.println(((x * x + y * y <= 1) && (y >= Math.abs(x))) ? Math.sqrt(Math.abs(x * x - 1)) : x + y);

}

Решение.

Через переменные x, y обозначим координаты точки.

Мы имеем 3 графика функций:

[latex]y=-x[/latex]
[latex]y=x[/latex]
[latex]x^{2}+y^{2}=1[/latex]

Проверяем находится ли точка в заштрихованной области. Точка обязательно должна находиться над или на оси x.

Если точка принадлежит данной области то для расчёта u используем формулу:

[latex]\sqrt{|x^{2}-1|}[/latex]

В противном случае формулу:

[latex]u=x+y[/latex]

Related Images:

Ragnarök — Power of Thor

12/10/2014 by Байков Дмитро

Четвертая по счету игра на сайте называется Ragnarök — Power of Thor, где нам посчастливилось быть Великим Воином Тором. Тору необходимо самым кратчайшим путем добраться до источника энергии, которая придаст ему еще больше сил и уверенности в дальнейших сражениях.

Пока еще не всемогущий Тор ждет указаний

Инициализация

В начале нам сообщают положение на карте источника и самого персонажа (их координаты по X и Y) (int LX, LY) (int TX, TY) соответственно.

Игровой цикл

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

Вход

В самом игровом цикле нам сообщают величину энергии Тора (int E), которая уменьшается на 1 с каждым последующим ходом.

Выход

В выходной поток необходимо вывести одну строку. Нам представлено всего 8 возможных вариантов дальнейшего передвижения Тора. Screenshot_2222

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

Перевод строки на новую обязателен.

Тест 1

Запуская программу впервые, Тор будет сам не свой, двигаясь совсем не по направлению к источнику.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;

        cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1) {

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

// Write an action using cout. DON'T FORGET THE "<< endl"

// To debug: cerr << "Debug messages..." << endl;

cout << "SE" << endl; // A single line providing the move to be made: N NE E SE S SW W or NW

}

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

Адекватное решение

Немного подумав вспоминаем, что нам даны начальные координаты как источника так и энергии. Сразу же приходит в голову мысль, что их надо сравнивать.

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

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

Если равны координаты Тора и источника энергии по X, то тут мы находим разность координат источника и Тора по Y, если LY — TY > 0 (Источник находится выше Тора по оси Y), то идем на юг (вверх), в противном случае на север (вниз). Аналогично и с движением по Y, что дает нам силы пройти первые два теста.

Дважды заряженный энергией боец рвется подзарядиться и в третий раз, но вдруг остается стоять на месте. Обескураженный обстоятельствами Тор замечает, что источник уже находится не ровно по оси движения, а под каким-то определенным углом. Оставаясь на месте, Тор принимает обет молчания (не выводит ничего на экран) и погружается в свои мысли.

Цикл for идет на помощь

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

Код на C++:

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

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int LX; // the X position of the light of power
    int LY; // the Y position of the light of power
    int TX; // Thor's starting X position
    int TY; // Thor's starting Y position
    cin >> LX >> LY >> TX >> TY; cin.ignore();

    // game loop
    while (1) 
    {
        int E; // The level of Thor's remaining energy, representing the number of moves he can still make.
        cin >> E; cin.ignore();
        if (LX == TX) //Movement along the X axis.
        {
            if (( LY - TY ) < 0)
            {
            cout << "N" << endl;
            }
            else 
            {
            cout << "S" << endl;
            }
        }    
        if (TY == LY) //Movement along the Y axis.
        {
            if (( LX - TX ) < 0)
            {
            cout << "W" << endl;
            }
            else 
            {
                cout << "E" << endl;
            }
        }
        if (( LX - TX ) > 0) //Movement to the left half of the map
        {
            
            if (( LY - TY ) < 0)
            {
               for(int i = 0;i < abs ( LY - TY );i++)
               {
                    cout << "NE" << endl;
               }
                for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                {
                    cout << "E" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                 {
                    for(int i = 0;i < abs ( LY - TY );i++)
                    {
                        cout << "SE" << endl;
                    }
                   for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)
                    {
                        cout << "E" << endl;
                    }
                }
            }
        }
        if (( LX - TX ) < 0) //Movement to the right half of the map
        {
            
            if (( LY - TY ) < 0)
            {
                for(int i = 0;i < abs ( LY - TY );i++)
                {
                    cout << "NW" << endl;
                }
                for (int i=0;i < abs ( TX - ( LY - TY ));i++)
                {
                    cout << "W" << endl;
                }
            }
            else 
            {
                if (( LY - TY ) > 0)
                {
                   for (int i = 0;i < abs ( LY - TY );i++)
                   {
                        cout << "SW" << endl;
                   }
                    for (int i = 0;i< abs ( TX - ( LY - TY ));i++)
                    {
                        cout << "W" << endl;
                    }
                }
            }
        }
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <math.h>

using namespace std;

/**

* Auto-generated code below aims at helping you parse

* the standard input according to the problem statement.

**/

int main()

{

int LX; // the X position of the light of power

int LY; // the Y position of the light of power

int TX; // Thor's starting X position

int TY; // Thor's starting Y position

cin >> LX >> LY >> TX >> TY; cin.ignore();

// game loop

while (1)

{

int E; // The level of Thor's remaining energy, representing the number of moves he can still make.

cin >> E; cin.ignore();

if (LX == TX) //Movement along the X axis.

{

if (( LY - TY ) < 0)

{

cout << "N" << endl;

}

else

{

cout << "S" << endl;

}

if (TY == LY) //Movement along the Y axis.

{

if (( LX - TX ) < 0)

{

cout << "W" << endl;

}

else

{

cout << "E" << endl;

}

if (( LX - TX ) > 0) //Movement to the left half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "SE" << endl;

}

for (int i = 0;i < abs ( LX - abs ( LY - TY ));i++)

{

cout << "E" << endl;

}

if (( LX - TX ) < 0) //Movement to the right half of the map

{

if (( LY - TY ) < 0)

{

for(int i = 0;i < abs ( LY - TY );i++)

{

cout << "NW" << endl;

}

for (int i=0;i < abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

else

{

if (( LY - TY ) > 0)

{

for (int i = 0;i < abs ( LY - TY );i++)

{

cout << "SW" << endl;

}

for (int i = 0;i< abs ( TX - ( LY - TY ));i++)

{

cout << "W" << endl;

}

Код на Java:

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

class Player 
{
    public static void main(String args[]) 
    {
    	Scanner in = new Scanner(System.in);
	    int lightX = in.nextInt(); // the X position of the light of power
	    int lightY = in.nextInt(); // the Y position of the light of power
	    int initialTX = in.nextInt(); // Thor's starting X position
	    int initialTY = in.nextInt(); // Thor's starting Y position
	
	    // game loop
	    while (true) 
	    {
	        int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.
	        if (lightX == initialTX) //Movement along the X axis.
	        {
	            if ((lightY - initialTY) < 0)
	            	System.out.println("N");
	            else 
	            	System.out.println("S");
	        }    
	        if (initialTY == lightY) //Movement along the Y axis.
	        {
	            if ((lightX - initialTX) < 0)
	            	System.out.println("W");
	            else 
	                System.out.println("E");
	        }
	        if ((lightX - initialTX) > 0) //Movement to the left half of the map
	        {
	            if ((lightY - initialTY) < 0)
	            {
	               for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    System.out.println("NE");
	               for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                   System.out.println("E");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                 {
	                    for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	                    	System.out.println("SE");
	               		for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)
	                		System.out.println("E");
	                }
	            }
	        }
	        if ((lightX - initialTX) < 0) //Movement to the right half of the map
	        {
	            
	            if ((lightY - initialTY) < 0)
	            {
	                for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("NW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	            }
	            else 
	            {
	                if ((lightY - initialTY) > 0)
	                {
	                   for(int i = 0;i < Math.abs(lightY - initialTY);i++)
	            		System.out.println("SW");
	                for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)
	                	System.out.println("W");
	                }
	            }
	        }
	    }
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

int lightX = in.nextInt(); // the X position of the light of power

int lightY = in.nextInt(); // the Y position of the light of power

int initialTX = in.nextInt(); // Thor's starting X position

int initialTY = in.nextInt(); // Thor's starting Y position

// game loop

while (true)

{

int remainingTurns = in.nextInt();// The remaining amount of turns Thor can move. Do not remove this line.

if (lightX == initialTX) //Movement along the X axis.

{

if ((lightY - initialTY) < 0)

System.out.println("N");

else

System.out.println("S");

}

if (initialTY == lightY) //Movement along the Y axis.

{

if ((lightX - initialTX) < 0)

System.out.println("W");

else

System.out.println("E");

}

if ((lightX - initialTX) > 0) //Movement to the left half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SE");

for (int i = 0;i < Math.abs(lightX - Math.abs(lightY - initialTY));i++)

System.out.println("E");

}

if ((lightX - initialTX) < 0) //Movement to the right half of the map

{

if ((lightY - initialTY) < 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("NW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

else

{

if ((lightY - initialTY) > 0)

{

for(int i = 0;i < Math.abs(lightY - initialTY);i++)

System.out.println("SW");

for (int i=0;i < Math.abs(initialTX - (lightY - initialTY));i++)

System.out.println("W");

}

Получается вот такой вот симпатичный код, описывающий все возможные ситуации по передвижению Тора (переносит Тора к источнику из любой точки карты). Разбивая на два возможных случая, движение в правой половине карты и в левой половине карты, получается, что программа охватывает любую ее точку. В самом цикле возьмем модуль между разностью (т.к. источник может находиться и ниже Тора). Сравниваем LX и TX, для того, чтобы узнать в какой половине карты находится источник. Если LX — TX > 0, то в цикле будем отнимать от LX, в противном случае — от TX, дабы не получить отрицательные значения. В конечном счете переменная E (энергия) там так и не понадобилось, так как воин и так находил кратчайшее расстояние.

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

Related Images:

А60в

05/10/2014 by Куленюк Денис Віталійович

рис.1

Задача. Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Найти [latex]u[/latex], если

где [latex]D[/latex] — заштрихованная область на (рис.1)

[latex]x[/latex]	[latex]y[/latex]	[latex]u[/latex]	Комментарий
5	3	22	Точка не входит в D
0.5	0.5	0	Точка входит в D
0	0	0	Тoчка лежит на границе D

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

Вот те самые вышеупомянутые уравнения:
1)[latex]y=1-{ x }^{ 2 }[/latex]
2)[latex]{ x }^{ 2 }+{ (y-1) }^{ 2 }=1[/latex]

Второе уравнение можно привести к виду:
[latex]y=1\pm\sqrt{1-{x}^{2}} [/latex] Заметим что указанная формула работает только при: [latex]{ x }\le 1[/latex](Важно не забыть упомянуть об этом в местах в участках кода которых мы будем её использовать).
Исходя из выше наведенного графика: нас интересует нижняя часть окружности, тогда на месте [latex]\pm[/latex] нужно поставить [latex]-[/latex]
Также график показывает нам что координата [latex]y[/latex] заданной нам точки должна быть:
[latex]1-\sqrt { 1-{ x }^{ 2 } }<y<1-{ x }^{ 2 }[/latex]

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

Сам код программы: http://ideone.com/SMyaWK

#include <cstdlib>
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
	double x, y, u;
	cin >> x >> y;
 
	if( x<=1 && x>=-1 && y>=( 1-sqrt( 1-x*x ) ) && y<=(1-x*x) )
	{
		u = x-y;
	
	}else{
			u = x*y+7;
		 }
	cout << u << endl;
}