Форум программистов, компьютерный форум CyberForum.ru

Максимальный периметр - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Mashka13330
0 / 0 / 0
Регистрация: 02.04.2013
Сообщений: 14
04.04.2013, 19:03     Максимальный периметр #1
Среди исходных точек найдите три, образующие треугольник с максимальным периметром. Выведите данный периметр.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Формат входных данных

Программа получает на вход набор точек на плоскости. Сначала задано количество точек n (2<n<101), затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Все исходные координаты – целые числа, не превосходящие 103.

Формат выходных данных

Необходимо вывести найденный периметр с точностью в 15 значащих цифр.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2013, 19:03     Максимальный периметр
Посмотрите здесь:

C++ периметр треугольника
C++ Максимальный элемент матрицы заменить на нуль и вывести на печать угол матрицы, в котором расположен этот максимальный элемент
Максимальный элемени матрицы заменить на нуль и вывести на печать угол матрицы, в котором расположен этот максимальный элемент C++
C++ Найти периметр четырехугольника
C++ Все отрицательные элементы заданного массива L (11) разделить на максимальный элемент этого массива. Вывести максимальный элемент, начальный и преобра
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
04.04.2013, 23:40     Максимальный периметр #2
Кроме структуры Point понадобится еще и структура Triangle

C++
1
2
3
4
5
6
7
8
9
10
struct Point
{   int x,y;
};
 
struct Triangle
{   Point A[3];
    double side[3];
    double perimeter;
    bool exist;
};
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.04.2013, 08:47     Максимальный периметр #3
Вариант прямым перебором. Конечно, можно оптимизировать с помощью матрицы расстояний и поиска максимальной петли, но будет дюже хитро.
Не люблю консольный ввод, поэтому задаю случайными числами. Прокомментировал, где поправить.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
 
 
struct Point {
  int x, y;
  Point() : x(0), y(0) {}
  Point(int x, int y) : x(x), y(y) {}
};
 
double getDistance(const Point &a, const Point &b) {
  return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
};
 
int main(int argc, char *argv[]) {
  srand(time(0));
 
  int numberOfPoints = 3 + rand() % 88; // считать вместо задания числом
  Point *points = new Point[numberOfPoints];
  
  for (int i = 0; i < numberOfPoints; ++i) {
    // считать вместо задания случайным значением
    points[i] = Point(rand() % 103, rand() % 103);
  }
  
  double maximumPerimeter = 0.0;
  for (int i = 0; i < numberOfPoints - 2; ++i) {
    for (int j = i + 1; j < numberOfPoints - 1; ++j) {
      double sideA = getDistance(points[i], points[j]);
      for (int k = j + 1; k < numberOfPoints; ++k) {
        double sideB = getDistance(points[i], points[k]);
        double sideC = getDistance(points[j], points[k]);
        double perimeter = sideA + sideB + sideC;
        if (perimeter > maximumPerimeter) {
          maximumPerimeter = perimeter;
        }
      }
    }
  }
  std::cout << maximumPerimeter << std::endl;
  
  delete [] points;
 
  std::cin.get();
  return 0;
}
IrineK
Заблокирован
05.04.2013, 10:10     Максимальный периметр #4
lemegeton, не каждые три стороны образуют треугольник. Это необходимо учесть.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.04.2013, 10:12     Максимальный периметр #5
Цитата Сообщение от IrineK Посмотреть сообщение
lemegeton, не каждые три стороны образуют треугольник. Это необходимо учесть.
Отрезки между любыми тремя точками образуют треугольник.
IrineK
Заблокирован
05.04.2013, 10:19     Максимальный периметр #6
Не всегда:
1) если три точки лежат на одной прямой - треугольник не построишь
2) при рандомном присвоении значений вы не застрахованы от совпадающих точек.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.04.2013, 10:25     Максимальный периметр #7
Это называется вырожденный треугольник. Даже если все три точки вообще совпадают.

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

По моему опыту, чаще попадает -- в словосочетании "вырожденный треугольник" есть слово "треугольник".
IrineK
Заблокирован
05.04.2013, 10:31     Максимальный периметр #8
Риск проиграть в этой лотерее все же есть )
Избежать его очень просто:

C++
1
2
3
inline bool triangleExists(Point p[])
{   return ((p[0].x-p[2].x)*(p[1].y-p[2].y) != (p[1].x-p[2].x)*(p[0].y-p[2].y));
}
Особые точки, вырожденные случаи и т.п. должны учитываться прогером - за это платят )
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.04.2013, 11:18     Максимальный периметр #9
Overengineering.

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

Цитата Сообщение от IrineK Посмотреть сообщение
за это платят
В случае, когда платят, такие вопросы решаются на уровне требований или ТЗ.

Добавлено через 5 минут
Цитата Сообщение от IrineK Посмотреть сообщение
Риск проиграть в этой лотерее все же есть )
Избежать его очень просто:
Не вводите в заблуждение. Это не избегание риска проиграть, это ставка на другую лошадь.
IrineK
Заблокирован
05.04.2013, 11:32     Максимальный периметр #10
Итак - вопрос терминологии и дело вкуса )
С точки зрения цели исследования осталось выяснить: каким образом определяется периметр вырожденного треугольника в этом дискурсе? )
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
05.04.2013, 14:46     Максимальный периметр #11
крутой прогер должен хотя бы слегка знать геометрию...

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

Добавлено через 1 минуту
могу дать вам только один совет по подобным задачам: сортируйте инпут - это эффективнее.
IrineK
Заблокирован
06.04.2013, 00:52     Максимальный периметр #12
salam, в этой задаче говорим не о сторонах, а о точках.

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

Для сторон double треугольника, заданного точками int, если вы их считаете в самой проге, вас могут ждать неприятные сюрпризы. Казалось бы, проверочная функция (каждая сторона должна быть больше суммы двух других):
C++
1
2
3
inline bool triangleExists(double a[])
{   return (a[0]+a[1]>a[2]) && (a[1]+a[2]>a[0]) && (a[2]+a[0]>a[1]);
}
но в силу особенностей double вы получите ответ, что треугольник со сторонами, например: sqrt(2), 3*sqrt(2), 4*sqrt(2) - существует.

Если стороны double вводятся вручную, то проблемы быть не должно (мы редко вводим что-то с точностью большей чем 6 знаков после запятой), а вот если они определяются по ходу - жди сюрпризов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 16:58     Максимальный периметр
Еще ссылки по теме:

C++ Заменить максимальный элемент в матрице, средним арифметическим элементов строки, в которой находится максимальный элемент
C++ найти максимальный элемент массива x(15) . переставить местами этот максимальный элемент с индексом 4
C++ Найти максимальный элемент (из 10 чисел) и следующий за ним максимальный элемент

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.04.2013, 16:58     Максимальный периметр #13
Цитата Сообщение от IrineK Посмотреть сообщение
double треугольника, заданного точками int, если вы их считаете в самой проге, вас могут ждать неприятные сюрпризы.
я всегда думал, что программист сам определяет, как он хранит данные... никто не покарает вас при наличии в условии фразы "целые координаты" хранить точки как пары даблов...
Yandex
Объявления
06.04.2013, 16:58     Максимальный периметр
Ответ Создать тему
Опции темы

Текущее время: 10:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru