Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.11.2018, 18:44   #1
else aaa
Новичок
Джуниор
 
Регистрация: 12.11.2018
Сообщений: 2
По умолчанию Сортировка массива структур методом вставки

Нужна помощь со сборкой задачи.

Задача: Соединить конечное множество точек на плоскости замкнутой линией без самопересечений с вершинами в этих точках.(Ответом будет порядок обхода точек плоскости). Подсказка: перейти к полярным координатам и упорядочить точки по значениям угла, а для точек с одинаковым значением угла -по расстоянию до полюса.Используйте алгоритм сортировки вставками.

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

Сделал массив структур, задал их, перевёл с помощью функции координаты в полярные. И дальше проблема - сортировка. Я в ней не шарю. Отсортировал значения углов точек, а их сами нет. Нужно как-то отсортировать точки по сначала оп углам(у), а потом те, которые в значениях углов совпадают, отсортировать по значению радиуса. Помогите пожалуйста, скоро сдавать.
Код:
#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;

struct Point
{
	double x;
	double y;
};

void conv(double& x1, double& y1)
{
	double rad = sqrt(x1*x1 + y1*y1),
		ygol = acos(x1 / rad);
	x1 = rad;
	y1 = ygol;
}

int main()
{
	const int N = 10;
	setlocale(LC_ALL, "Russian");
	Point A[N];
	for (int i = 0; i < N; i++)
	{
		cout << "Введите координаты точки номер " << i + 1 << ":   ";
		cin >> A[i].x >> A[i].y;
		cout << "Точка номер " << i + 1 << " с декартовыми координатами " << A[i].x << ";" << A[i].y << endl;
		conv(A[i].x, A[i].y);
		cout << "Данная точка имеет полярные координаты " << A[i].x << ";" << A[i].y << endl;
	}
	int max, num, k=0;
	while (k < N)
	{
		max = INT_MIN;
		for (int i = N - 1; i >= k; i--)
		{
			if (A[i].y > max)
			{
				max = A[i].y;
				num = i;
			}
		}
		for (int i = num; i >= k; i--)
		{
			A[i].y = A[i - 1].y;
		}

		A[k].y = max;
		k++;
	}
		cout << "Точки отсортирован\n";
		for (int i = 0; i < N; i++)
		{
			cout << A[i].y<< " ";
		}
	
	system("pause");
	return 0;
}

Последний раз редактировалось else aaa; 12.11.2018 в 18:47.
else aaa вне форума Ответить с цитированием
Старый 12.11.2018, 20:09   #2
else aaa
Новичок
Джуниор
 
Регистрация: 12.11.2018
Сообщений: 2
По умолчанию

В общем, я смог, но есть большая проблема. Сортировка не вставками. Помогите, я не знаю, как это блин делать.
Код:
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <time.h>
using namespace std;
struct Point
{
	int ind;     // исходный индекс точки, что бы сохранить порядок при сортировке
	double x;    // координата X
	double y;    // координата Y
	double a;    // угол в градусах
	double r;    // радиус

	void conv() // посчитать <a> и <r>
	{
		r = sqrt(x*x + y*y);

		if (r == 0.0)
		{
			a = 0.0;
		}
		else
		{
			a = 180.0 * acos(x / r) / acos(-1.0);
			if (y < 0)
				a += 180;
		}
	}

	int compare(Point &right) // сравнить this (левый операнд) с указанной структурой <right> (правый операнд)
	{
		if (a < right.a)
			return -1; // меньше
		if (a > right.a)
			return 1; // больше

		// углы равны, сравниваем радиус

		if (r < right.r)
			return -1; // меньше
		if (r > right.r)
			return 1; // больше

		return 0; // точки совпадают
	}
};

int main()
{
	const int N=10;
	srand((unsigned int)time(0));

	Point points[N];

	// инициализация
	for (int i = 0; i < N; i++)
	{
		points[i].ind = i;
		points[i].x = 200 * rand() / RAND_MAX - 100;
		points[i].y = 200 * rand() / RAND_MAX - 100;

		points[i].conv();
		cout << i + 1 << ") (x=" << points[i].x << ", y=" << points[i].y << ") - (a=" << points[i].a << ", r=" << points[i].r << ")" << endl;
	}

	// сортировка
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (points[i].compare(points[j]) > 0)
			{
				Point temp = points[i];
				points[i] = points[j];
				points[j] = temp;
			}
		}
	}

	// результат сортировки
	cout << endl;
	for (int i = 0; i < N; i++)
	{
		std::cout << points[i].ind + 1 << ") a=" << points[i].a << ", r=" << points[i].r << endl;
	}
	cout << endl;

	system("pause");
	return 0;
else aaa вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сортировка массива методом вставки - Pascal ABC Korban Паскаль, Turbo Pascal, PascalABC.NET 3 15.03.2017 04:21
[C++]: сортировка методом вставки erfo Помощь студентам 3 23.05.2012 16:13
И снова я. Сортировка методом вставки! xitrec1zaraza Общие вопросы C/C++ 3 07.12.2010 09:48
Сортировка двумерного массива методом вставки. Pascal xXxalexXx Помощь студентам 0 25.11.2010 20:03
Сортировка массива методом линейной вставки☺ m-o-r-t-r-o-m Фриланс 6 04.11.2009 14:59