Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.423 RSS
←   Май 2016   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.423 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 476
∙ повысить рейтинг » 		D-mon55
Статус: 2-й класс
Рейтинг: 75
∙ повысить рейтинг » 		Асмик Гаряка
Статус: Советник
Рейтинг: 68
∙ повысить рейтинг »

∙ С / С++

Номер выпуска:1860
Дата выхода:14.05.2016, 15:21
Администратор рассылки:Андрей Кузнецов aka Dr_Andrew (Старший модератор)
Подписчиков / экспертов:19 / 14
Вопросов / ответов:1 / 1

Консультация # 189331: Здравствуйте, уважаемые эксперты! Помогите, пожалуйста! Реализовать решение задачи на Си: выбрать три различных точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами точек, лежащих внутри и вне треугольника с вершинами в выбранных точках. ...

Консультация # 189331:

Здравствуйте, уважаемые эксперты! Помогите, пожалуйста!
Реализовать решение задачи на Си: выбрать три различных точки из заданного множества точек на плоскости так, чтобы была минимальной разность между количествами точек, лежащих внутри и вне треугольника с вершинами в выбранных точках.

Дата отправки: 09.05.2016, 14:53
Вопрос задал: YarLam125 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, YarLam125!
Посмотрите, как я сделал:
1) Задаются случайно 100 точек (можете переделать на ручной ввод или изменить число точек)
2) Перебираем все тройки чисел, для каждой пробегаем по всем остальным точкам и считаем
количество попаданий внутрь треугольника.
3) Ищем ту тройку, у которой число попаданий во внутрь ближе к половине количества точек.
4) Попадание вовнутрь определяем по тому, находится ли точка по одну сторону с каждой вершиной
треугольника относительно прямой, соединяющей две оставшиеся вершины. (см. аналитическую геометрию)
5) выводится количество внутренних точек. Можете самостоятельно вывести координаты найденных точек, они сохраняются в a, b, c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
 
#define	N	100

typedef struct point 
{
	double x;
	double y;
};
 
// Вычисляет положение точки D(x,y) относительно прямой AB
double g(point a, point b, point d) 
{
	return (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x);
}
 
// Лежат ли точки C и D с одной стороны прямой (AB)?
bool f(point a, point b, point c, point d) 
{
	return g(a, b, c) * g(a, b, d) >= 0;
}
 
int main() 
{
	point*	p = (point*)malloc(N*sizeof(point));;
	int		i,j,k,m;
	int		ci;
	int		ci_curr;
	point	a,b,c;

	srand(time(NULL));

	for(i=0; i<N; i++)
	{
		p[i].x = (rand()%200) - 100;
		p[i].y = (rand()%200) - 100;
	}

	ci = 0;
	for(i=0; i<N-2; i++)
	{
		for(j=i+1; j<N-1; j++)
		{
			for(k=j+1; k<N; k++)
			{
				ci_curr = 0;
				for(m=0; m<N; m++)
				{
					if ((m != i) && (m != j) && (m != k))
						ci_curr += f(p[i],p[j],p[k],p[m]) && f(p[j],p[k],p[i],p[m]) && f(p[k],p[i],p[j],p[m]);
				}
				if (abs(ci_curr - N/2) < abs(ci - N/2))
				{
					ci = ci_curr;
					a = p[i];
					b = p[j];
					c = p[k];
				}
			}
		}
	}
	printf("ci = %d\n", ci);
	
	free(p);
	return 0;
}

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 10.05.2016, 02:41
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное