e-olymp 239. Треугольники

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

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные	Выходные данные
5 2 -1 3 0 0 4 -3 0 -2 1	6
5 0 0 2 4 6 6 10 34 -42 -48	10
4 0 0 0 1 1 0 1 1	0
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2	24
5 0 0 0 1 -1 0 -1 -1 3 -3	3

#include <iostream>
using namespace std;
 
int main() {
    unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};
    unsigned long long c = 0;
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> x1 >> y1;
        if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;
        else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;
        else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;
        else A [3] ++;
    }
    for(int i = 0; i < 4; i ++){
        for(int  j= 0; j < 4; j ++){
            if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;
            else c += A[i] * (A[i] - 1) * A[j] / 2;
        }       
    }
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};

unsigned long long c = 0;

cin >> n;

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

cin >> x1 >> y1;

if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;

else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;

else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;

else A [3] ++;

}

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

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

if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;

else c += A[i] * (A[i] - 1) * A[j] / 2;

}

cout << c;

return 0;

}

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

Related Images:

e-olymp 932. Высота треугольника

04/12/2017 by Валерия Ларикова

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа: [latex]S (0 < S ≤ 100), и[/latex] [latex]a[/latex] ([latex]\left | a \right |[/latex] ≤ 100).

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

Искомая высота с точностью до сотых.

Тесты

#	Входные данные	Выходные данные
1	20 7	3.73
2	35 3	7.00
3	12 4	3.29
4	67 9	7.92
5	135 13	11.17

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

#include <iostream>
#include <cmath>//данная библиотека позволяет извлекать корень квадратный
#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой
using namespace std;
 
int main() {
    int s, a;//площадь треугольника,разность основания и высоты 
    int d;//дискриминант 
    double h, dk;// высота треугольника, корень квадратный из дискриминанта  
    cin >> s >> a; 
    d = a*a + 8*s;//формула для нахождения дискриминанта 
    dk = sqrt(d);//извлекаем корень квадратный из дискриминанта 
    h = (-a + dk)/2;//формула для нахождения высоты треугольника
    cout << fixed << setprecision(2) << h;// функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков
 
    return 0;
}

#include <iostream>

#include <cmath>//данная библиотека позволяет извлекать корень квадратный

#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой

using namespace std;

int main() {

int s, a;//площадь треугольника,разность основания и высоты

int d;//дискриминант

double h, dk;// высота треугольника, корень квадратный из дискриминанта

cin >> s >> a;

d = a*a + 8*s;//формула для нахождения дискриминанта

dk = sqrt(d);//извлекаем корень квадратный из дискриминанта

h = (-a + dk)/2;//формула для нахождения высоты треугольника

cout << fixed << setprecision(2) << h;// функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков

return 0;

}

Алгоритм решения задачи

Формула для вычисления площади треугольника [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot c[/latex], где [latex]h[/latex] – высота, а [latex]c[/latex] – сторона, к которой высота проведена.
В задаче сказано, что основание больше высоты на величину [latex]a[/latex]. Значит вместо [latex]c[/latex] мы можем подставить в формулу [latex]h+a[/latex]. Теперь формула приобретает следующий вид: [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot \left (h+a \right )[/latex]
Cовершив некоторые преобразования приходим к квадратному уравнению [latex]h^{2}+a\cdot h-2\cdot S = 0[/latex]
Далее находим дискриминант по формуле [latex]D = a^{2}+4\cdot2\cdot S[/latex]. Находим корень квадратный из дискриминанта [latex]\sqrt{D}[/latex]
Находим высоту по формуле [latex]h=\frac{-a+\sqrt{D}}{2}[/latex]
Второй корень нам не подходит, потому что он меньше [latex]0[/latex], а длина не может быть отрицательной.
Подставляем исходные данные в формулы, получаем результат.

Также подробное описание представлено в коде программы.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

Related Images:

e-olymp 926. Формула Герона

23/11/2017 by Артем Чернобровкин

Задача

Герон Александрийский

Задано стороны [latex]a, b, c, d[/latex] и диагональ [latex]f[/latex] выпуклого четырехугольника. Определить площадь четырехугольника, используя вспомогательную функцию вычисления площади треугольника по формуле Герона.

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

В одной строке задано 5 действительных чисел [latex] a, b, с, d, f[/latex] [latex](0 < a, b, c, d, f ≤ 100)[/latex], как показано на рисунке.

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

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

Тесты

#	Входные данные	Выходные данные
1	2 2 2 2 2	3.4641
2	7 7 5 6 2	11.6120
3	9 5 3 2 4	2.9047
4	5 7 2 3 4	12.7027
5	7 8 6 2 5	22.0043

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

#include <iostream>
#include <cmath>//данную библиотеку подключаем  для того, чтобы была возможность извлечь корень
#include <iomanip>//данную библиотеку подключаем для того, чтобы установить кол-во знаков после запятой
using namespace std;

int main() {
    double a,b,c,d,f;//длины сторон треугольника
    double S1,S2,SO;//площади треугольников и общая площадь соответственно
    double P1,P2,p1,p2;//периметр и полупериметр соотвественно
    double G1,G2;//выражение под корнем
    cin>>a>>b>>c>>d>>f;
    P1= a+b+f;//периметр первого треугольника
    p1= P1/2;//полупериметр первого треугольника
    P2= d+c+f;//периметр второго треугольника
    p2= P2/2;//полупериметр второго  треугольника
    G1=p1*(p1-a)*(p1-b)*(p1-f);//выражение под корнем 
    S1=sqrt(G1);//пользуясь формулой Герона извлекаем корень
    //аналогично для второго треугольника
    G2=p2*(p2-d)*(p2-c)*(p2-f);
    S2=sqrt(G2);
    SO=S1+S2;//находим общую площадь фигуры состоящую из двух треугольников
    cout<<fixed<<setprecision(4)<<SO;
    return 0;
}

#include <iostream>

#include <cmath>//данную библиотеку подключаем для того, чтобы была возможность извлечь корень

#include <iomanip>//данную библиотеку подключаем для того, чтобы установить кол-во знаков после запятой

using namespace std;

int main() {

double a,b,c,d,f;//длины сторон треугольника

double S1,S2,SO;//площади треугольников и общая площадь соответственно

double P1,P2,p1,p2;//периметр и полупериметр соотвественно

double G1,G2;//выражение под корнем

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

P1= a+b+f;//периметр первого треугольника

p1= P1/2;//полупериметр первого треугольника

P2= d+c+f;//периметр второго треугольника

p2= P2/2;//полупериметр второго треугольника

G1=p1*(p1-a)*(p1-b)*(p1-f);//выражение под корнем

S1=sqrt(G1);//пользуясь формулой Герона извлекаем корень

//аналогично для второго треугольника

G2=p2*(p2-d)*(p2-c)*(p2-f);

S2=sqrt(G2);

SO=S1+S2;//находим общую площадь фигуры состоящую из двух треугольников

cout<<fixed<<setprecision(4)<<SO;

return 0;

}

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

Дано

Фигура, состоящая из двух треугольников;

Цель

Посчитать площадь данной фигуры;

Идея

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

Способ решения

Вспомним формулу Герона [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)}[/latex].
Поймем, что нам не хватает некоторых данных, а именно [latex]p[/latex].
Понимаем, что [latex]p[/latex] — это полупериметр, который находится по формуле [latex]p=\frac{P}{2}[/latex].
Возникает вопрос, что такое [latex]P[/latex] ? Приходим к выводу, что это периметр.
Находим формулу периметра, который равен [latex]P=a+b+c[/latex]. Данная формула была подведена под условие нашей задачи.
После того как мы вывели формулы, можем приступать к решению задачи.
Подставляя исходные данные в формулы, которые были представлены выше, получаем результат.
Более подробное описание каждого действия представлено выше в коде. Это сделано для того, чтобы пользователь получал ответы на интересующие его вопросы непосредственно в момент их возникновения.

Ссылки

Задача на e-olymp

Код задачи на ideone

Related Images:

Ю1.23

19/09/2014 by Карташов Денис Геннадійович

Задача

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

Тесты:

[latex]x_{1}[/latex]	[latex]y_{1}[/latex]	[latex]x_{2}[/latex]	[latex]y_{2}[/latex]	[latex]x_{3}[/latex]	[latex]y_{3}[/latex]	Результат	Прохождение теста
0	4	0	7	0	2	Не является треугольником…	Пройден
51	0	97	0	68	0	Не является треугольником…	Пройден
1	7	3	13	6	22	Не является треугольником…	Пройден
0	3	0	0	4	0	10.3775	Пройден
0	0	1	1.7320	2	0	5.1960	Пройден

Исходный код программы:

#include <stdio.h>
#include <math.h>
 
int main() {      
    double x1,y1,x2,y2,x3,y3; //координаты вершин//
    double AF,BM,CN,P; //обозначения медиан и их суммы//
    printf("Введите координаты точки А\n");              
    scanf("%lf %lf",&x1,&y1);
    printf("Введите координаты точки B\n");
    scanf("%lf %lf",&x2,&y2);
    printf("Введите координаты точки C\n");
    scanf("%lf %lf",&x3,&y3);
    if((x1==x2&&x2==x3)||(y1==y2&&y2==y3)||((y2-y1)*(x3-x1)-(x2-x1)*(y3-y1)==0)) //Рассмотрение частных случаев//
    	printf("Не является треугольником, так как данные точки лежат на одной прямой \n");
    else {
       //Вычисления длин медиан;xF,yF,xM,yM,xN,yN;-координаты середин сторон треугольника//
       AF=sqrt(pow(x1-(x3+x2)/2,2)+pow(y1-(y3+y2)/2,2));   //xF=(x3+x2)/2,yF=(y3+y2)/2;//
       BM=sqrt(pow((x1+x3)/2-x2,2)+pow((y1+y3)/2-y2,2));   //xM=(x1+x3)/2, yM=(y1+y3)/2;//
       CN=sqrt(pow((x1+x2)/2-x3,2)+pow((y1+y2)/2-y3,2));   //xN=(x1+x2)/2, yN=(y1+y2)/2;//
       P=AF+BM+CN;//Вычисление суммы//
       printf("Сумма медиан треугольника ABC равна: %.4lf" ,P);
    }
    return 0;
    
}

#include <stdio.h>

#include <math.h>

int main() {

double x1,y1,x2,y2,x3,y3; //координаты вершин//

double AF,BM,CN,P; //обозначения медиан и их суммы//

printf("Введите координаты точки А\n");

scanf("%lf %lf",&x1,&y1);

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

scanf("%lf %lf",&x2,&y2);

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

scanf("%lf %lf",&x3,&y3);

if((x1==x2&&x2==x3)||(y1==y2&&y2==y3)||((y2-y1)*(x3-x1)-(x2-x1)*(y3-y1)==0)) //Рассмотрение частных случаев//

printf("Не является треугольником, так как данные точки лежат на одной прямой \n");

else {

//Вычисления длин медиан;xF,yF,xM,yM,xN,yN;-координаты середин сторон треугольника//

AF=sqrt(pow(x1-(x3+x2)/2,2)+pow(y1-(y3+y2)/2,2)); //xF=(x3+x2)/2,yF=(y3+y2)/2;//

BM=sqrt(pow((x1+x3)/2-x2,2)+pow((y1+y3)/2-y2,2)); //xM=(x1+x3)/2, yM=(y1+y3)/2;//

CN=sqrt(pow((x1+x2)/2-x3,2)+pow((y1+y2)/2-y3,2)); //xN=(x1+x2)/2, yN=(y1+y2)/2;//

P=AF+BM+CN;//Вычисление суммы//

printf("Сумма медиан треугольника ABC равна: %.4lf" ,P);

}

return 0;

}

Алгоритм:

Вводим переменные;
Вводим координаты точек [latex]A[/latex], [latex]B[/latex], [latex]C[/latex];
Используем условный оператор для выделения частного случая.
- Если точки будут лежать на одной прямой, то медиан, как и самого треугольника не может быть в принципе. Для проверки используем уравнение прямой, проходящей через две несовпадающие точки: [latex]\frac{y-y_{1}}{y_{2}-y_{1}}=\frac{x-x_{1}}{x_{2}-x_{1}}[/latex]. С помощью эквивалентных преобразований получаем формулу:[latex]\left(y_{2}-y_{1} \right) \left(x-x_{1}\right)-\left(y-y_{1} \right) \left(x_{2}-x_{1}\right)=0[/latex] c помощью которой (подставив вместо [latex]x[/latex] и [latex]y[/latex] [latex]x_{3}[/latex] и [latex]y_{3}[/latex] соответственно) сможем определить, находятся ли данные точки на одной прямой).
- В случае, если точки не находятся на одной прямой, находим длины отрезков соединяющих середины сторон с противоположными им вершинами(эти отрезки и являются медианами); (Координаты середин отрезков находим по формулам: [latex]\frac{\left(x_{1}+x_{2} \right)}{2}[/latex], [latex]\frac{\left(y_{1}+y_{2} \right)}{2}[/latex], где [latex]\left(x_{1};y_{1} \right)[/latex] и [latex]\left(x_{2};y_{2} \right)[/latex] — координаты концов отрезка, середину которого мы находим. Длину медианы находим по формуле: [latex]AB=\sqrt{\left(x_{1}-x_{2} \right)^{2}+\left(y_{1}-y_{2} \right)^{2}}[/latex] , где [latex]\left(x_{1};y_{1} \right)[/latex] и [latex]\left(x_{2};y_{2} \right)[/latex] — координаты точек [latex]A[/latex] и [latex]B[/latex] соответственно).
Находим сумму длин этих отрезков. (Простое сложение).

Related Images:

А47

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

Задача:
Даны действительные положительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex].
а) Выяснить существует ли треугольник с длинами сторон [latex]x[/latex], [latex]y[/latex], [latex]z[/latex].
б) Если треугольник существует, то ответить — является ли он остроугольным?

NA — «not acute» — существует, но не остроугольный
A — «acute» — остроугольный
DE — «doesn’t exist» — не существует

[latex]x[/latex]	[latex]y[/latex]	[latex]z[/latex]	Результат	Комментарий:
3	4	5	NA	Пройден: трегольник прямоугольный
1.30	3.86	5.14	NA	Пройден
1.67	2.29	8	NE	Пройден: нарушено условие (I)
811	22	790	NA	Пройден: треугольник тупоугольный
10	11	12	A	Пройден

#include 
#include 
using namespace std;

int main()
{
    double x, y, z;
	scanf( "%lf %lf %lf", &x, &y, &z );
	
	//find the longest side
	if ( x > y ) swap( x, y );
	if ( y > z ) swap( y, z );
	
    //if the triangle exists
    if( x + y > z )
    {
        //if it is acute
        double COS_VALUE = ( x*x + y*y - z*z ) / ( 2*x*y );
        if( COS_VALUE > 0 ) printf( "The triangle is acute." );
        else printf( "The triangle is not acute." );
    }
    else printf( "The triangle doesn't exist." );
    return 0;
}

#include

using namespace std;

int main()

{

double x, y, z;

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

//find the longest side

if ( x > y ) swap( x, y );

if ( y > z ) swap( y, z );

//if the triangle exists

if( x + y > z )

{

//if it is acute

double COS_VALUE = ( x*x + y*y - z*z ) / ( 2*x*y );

if( COS_VALUE > 0 ) printf( "The triangle is acute." );

else printf( "The triangle is not acute." );

}

else printf( "The triangle doesn't exist." );

return 0;

}

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

class Triangles
{
	public static double square(double num){ return num*num; }
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double s[] = new double[3];		
		for(int i = 0; i < 3; i++)
			s[i] = in.nextDouble();
		java.util.Arrays.sort(s);
		if(s[0] + s[1] <= s[2]){
			System.out.println("The triangle doesn't exist.");
		}
		else{
			double cosValue = Math.cos((square(s[0]) + square(s[1]) + square(s[2]))/(2*s[0]*s[1]));	
			if(cosValue > 0) System.out.println("The triangle is acute.");
			else System.out.println("The triangle is not acute.");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

import java.text.*;

class Triangles

{

public static double square(double num){ return num*num; }

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

{

Scanner in = new Scanner(System.in);

double s[] = new double[3];

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

s[i] = in.nextDouble();

java.util.Arrays.sort(s);

if(s[0] + s[1] <= s[2]){

System.out.println("The triangle doesn't exist.");

}

else{

double cosValue = Math.cos((square(s[0]) + square(s[1]) + square(s[2]))/(2*s[0]*s[1]));

if(cosValue > 0) System.out.println("The triangle is acute.");

else System.out.println("The triangle is not acute.");

}

Алгоритм:
I. Необходимым и достаточным условием существования треугольника с тремя заданными сторонами является условие вида:
[latex] x + y > z[/latex] (вырожденный случай не рассматривается)

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

II. Вид треугольника определяется углом, лежащим против большей стороны:
[latex]\alpha \in [ 0; \frac{ \pi }{ 2 } ]\Leftrightarrow \cos{(\alpha)}>0[/latex]

Знак косинуса угла легко определить через теорему косинусов:
[latex]z^{ 2 }=x^{ 2 }+y^{ 2 }-2xy\cos { (\alpha ) } \\ \cos { (\alpha ) } =\frac { x^{ 2 }+y^{ 2 }-z^{ 2 } }{ 2xy }[/latex]

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

Программное решение состоит из двух этапов:
0. Поиск наибольшей стороны.
1. Проверка условия (I).
2. Проверка условия (II).

Функция swap() взята из заголовочного файла algorithm.
В программе использован тип данных с плавающей точкой и двойной точностью (для отображения действительных чисел).
Для выполнения программы и проверки тестов можно воспользоваться следующим объектом. (реализация на Java)