Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 12.10.2016
Сообщений: 78
1

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

29.05.2018, 13:10. Просмотров 2035. Ответов 3
Метки нет (Все метки)

Выбрать три различные точки из заданного множества точек на плоскости так,
чтобы разность между количеством точек, лежащих внутри треугольника, и количеством
точек, лежащих вне треугольника, с вершинами в выбранных точках была минимальной.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.05.2018, 13:10
Ответы с готовыми решениями:

Из заданного на плоскости множества точек выбрать три различные точки
Само задание звучит так: "Из заданного на плоскости множества точек выбрать три различные точки...

Из заданного на плоскости множества точек выбрать три различные точки
Здравствуйте, помогите пожалуйста написать программу: Из заданного на плоскости множества точек...

Работа С Массивами (Выбрать три различные точки из заданного множества точек на плоскости так...)
Задание: Выбрать три различные точки из заданного множества точек на плоскости так, чтобы была...

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

3
Объявлятель переменных
962 / 284 / 283
Регистрация: 24.09.2011
Сообщений: 1,043
29.05.2018, 15:27 2
Лучший ответ Сообщение было отмечено kava13 как решение

Решение

Я тут немного впал в ересь и из трёх вложенных циклов выхожу по goto. Если Вам это противно, то пишите — поправлю.
И данное решение ищет такой треугольник, чтобы количество точек внутри и снаружи было примерно одинаковым. Если же трактовать Ваше условие со всей математической дотошностью, то правильным решением будут три точки, образующие треугольник, в который не попадает ни одна другая точка. Внутри — ноль, а снаружи — все остальные. Разница между "внутри" и "снаружи" минимальна и составляет –(n–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
49
50
51
52
53
#include <iostream>
#include <cmath>
 
struct point {
    double x;
    double y;
};
 
double getArea(const point &a, const point &b, const point &c) {
    return fabs((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
}
 
bool inTriangle(const point &p, const point &a, const point &b, const point &c) {
    return (getArea(a, b, c) >= (getArea(p, b, c) + getArea(a, p, c) + getArea(a, b, p)));
}
 
int main()
{
    int n = 7;
    point p[n] = {{0,0},{1,1},{2,2},{5,0},{7,3},{0,5},{2,5}};
    int a, b, c;
    int difference = n;
    for (int i = 0; i < n-2; i++) {
        for (int j = i+1; j < n-1; j++) {
            for (int k = j+1; k < n; k++) {
                int tmp = 0;
                for (int x = 0; x < n; x++) {
                    if ((x-i)*(x-j)*(x-k)) {
                        if (inTriangle(p[x],p[i],p[j],p[k])) {
                            tmp++;
                        } else {
                            tmp--;
                        }
                    } else {
                        continue;
                    }
                }
                tmp = abs(tmp);
                if (tmp < difference) {
                    difference = tmp;
                    a = i;
                    b = j;
                    c = k;
                }
                if (tmp == 0) {
                    goto Find;
                }
            }
        }
    }
    Find:
    std::cout << a << ' ' << b << ' ' << c;
}
0
0 / 0 / 0
Регистрация: 12.10.2016
Сообщений: 78
31.05.2018, 18:47  [ТС] 3
Вы очень помогли. Подскажите, а какие теоремы/правила вы использовали в функциях, чтобы понять, что точка не лежит в треугольнике?
0
Объявлятель переменных
962 / 284 / 283
Регистрация: 24.09.2011
Сообщений: 1,043
31.05.2018, 19:56 4
Лучший ответ Сообщение было отмечено kava13 как решение

Решение

Цитата Сообщение от kava13 Посмотреть сообщение
Подскажите, а какие теоремы/правила вы использовали в функциях, чтобы понять, что точка не лежит в треугольнике?
Для треугольника ABC и точки P я вычисляю площади треугольников ABC, ABP, APC и PBC, после этого сравниваю площадь ABC и сумму площадей ABP, APC и PBC. Если площадь ABC меньше, значит точка Р лежит за его пределами.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.05.2018, 19:56

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

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

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

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

Из заданного множества точек на плоскости выбрать три разные точки A, B, C
Из заданного множества точек на плоскости выбрать три разные точки A, B, C, так, чтобы внутри...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.