Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Nike1995
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
1

Поиск четырехугольника удовлетворяющему условиям

17.02.2016, 00:55. Просмотров 256. Ответов 4
Метки нет (Все метки)

Задание: даны мн-во точек, найти выпуклый четырехугольник, такой, что разность площадей наименьшего и наибольшего треугольников(образованного диагоналями четырехугольника), минимальна.
Все вроде сделал, только не знаю как перебрать все четырехугольники на мн-ве точек!
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsFormsApplication2
{
    public partial class Form1 : Form
    {
        public int x, y;
        List<PointF> pnt = new List<PointF>();
        public float n, nx, ny;
        public String s;
        public int p = 0;
        float cos;
        bool key = true;
        float x_c, y_c;
        PointF ab, ao;
        float sum;
 
        public Form1()
        {
            InitializeComponent();
        }
 
        //вырисовываем точки
        private void ttt(float x, float y)
        {
            Pen MyPen = new Pen(Color.Black, 3);
            Graphics g = Graphics.FromHwnd(pictureBox1.Handle);
            g.DrawEllipse(MyPen, x - 5, y - 5, 10, 10);
        }
 
        // находим угол между векторами
        private float get_ugol(float a_x, float a_y, float b_x, float b_y,
                               float c_x, float c_y)
        {
            float s_x = 0, s_y = 0, t_x = 0, t_y = 0;
 
            s_x = b_x - a_x;
            s_y = b_y - a_y;
 
            t_x = c_x - a_x;
            t_y= c_y - a_y;
 
            float Pr_1 = s_x * t_x + s_y * t_y;
            double sqr1 = Math.Sqrt(s_x * s_x + s_y * s_y);
            double sqr2 = Math.Sqrt(t_x * t_x + t_y* t_y);
 
            cos = Pr_1 / ((float)sqr1 * (float)sqr2);
            return cos;
        }
 
        // считает площадь треугольника
        private float get_area(float x_1, float y_1, float x_2, float y_2, float x_3, float y_3)
        {
            float a_b, a_o;
            float sin, buf;
 
            ab.X = x_2 - x_1;
            ab.Y = y_2 - y_1;
 
            ao.X = x_3 - x_1;
            ao.Y = y_3 - y_1;
 
            a_b = (float)Math.Sqrt((double)(ab.X * ab.X) + (double)(ab.Y * ab.Y));
            a_o = (float)Math.Sqrt((double)(ao.X * ao.X) + (double)(ao.Y * ao.Y));
 
            buf = get_ugol(x_1, y_1, x_2, y_2, x_3, y_3);
            
            sin = (float)Math.Sqrt(1 - (double)(buf * buf));
            
            sum = (float)(a_b * a_o * sin) / 2;
 
            return sum;
        }
 
        // добавление точек в список
        private void button1_Click(object sender, EventArgs e)
        {
            PointF p1 = new PointF();
            p1.X = (float)numericUpDown1.Value;
            p1.Y = (float)numericUpDown2.Value;
            pnt.Add(p1);
 
            n = pnt.Count();
            for (int i = p; i < n; i++)
            {
                nx = pnt[i].X;
                ny = pnt[i].Y;
                s = (p+1) + "            " + nx.ToString() + "            " + ny.ToString();
                listBox1.Items.Add(s);
                s = "";
                ttt(nx, ny);
            }
            p++;      
        }
 
        // является ли четырехугольник вырожденным
        private bool is_convex(int i, int j, int k, int z)
        {
            double eps = 0.1;
            float c_1, c_2, c_3, c_4;
            double sum;
 
            c_1 = get_ugol(pnt[i].X, pnt[i].Y, pnt[j].X, pnt[j].Y, pnt[z].X, pnt[z].Y);
            c_2 = get_ugol(pnt[j].X, pnt[j].Y, pnt[i].X, pnt[i].Y, pnt[k].X, pnt[k].Y);
            c_3 = get_ugol(pnt[k].X, pnt[k].Y, pnt[j].X, pnt[j].Y, pnt[z].X, pnt[z].Y);
            c_4 = get_ugol(pnt[z].X, pnt[z].Y, pnt[k].X, pnt[k].Y, pnt[i].X, pnt[i].Y);
 
            sum = Math.Acos(c_1) * 180 / Math.PI + Math.Acos(c_2) * 180 / Math.PI +
                  Math.Acos(c_3) * 180 / Math.PI + Math.Acos(c_4) * 180 / Math.PI;
 
            if (360 - sum > eps)
            {
                key = false;
                return key;
            }
 
            return key;   
        }
 
        // поиск координат центра четырехугольника(пересечение диагоналей)
        private void centre(float x_1, float y_1, float x_2, float y_2,
                            float x_3, float y_3, float x_4, float y_4)
        {
            y_c = (x_3*(y_4-y_3)-y_3*(x_4-x_3)+y_1*(x_2-x_1)/(y_2-y_1)*(y_4-y_3)-x_1*(y_4-y_3))/
                  ((x_2-x_1)/(y_2-y_1)*(y_4-y_3)-(x_4-x_3));
            x_c = y_c*(x_2-x_1)/(y_2-y_1)-y_1*(x_2-x_1)/(y_2 - y_1)+x_1;
        }
 
        //поиск выпуклого четырехугольника
        private void button2_Click(object sender, EventArgs e)
        {
            float sum;
            bool g = is_convex(0,1,2,3);
            if (g) MessageBox.Show("Выпуклый");
            else MessageBox.Show("Вогнутый");
            centre(pnt[0].X, pnt[0].Y, pnt[2].X, pnt[2].Y, pnt[1].X, pnt[1].Y, pnt[3].X, pnt[3].Y);
            sum = get_area(pnt[0].X, pnt[0].Y, pnt[1].X, pnt[1].Y, x_c, y_c);
            
            //здесь должен быть перебор точек
            
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.02.2016, 00:55
Ответы с готовыми решениями:

Организовать поиск по List<T> по условиям
Добрый день. Подскажите как организовать поиск по List&lt;T&gt; по условиям, которые...

определение вида четырехугольника
C# Определение вида четырехугольника: трапеция или параллелограмм :gsad:...

Проверить выпуклость четырехугольника
подскажите пожалуйста задан четырехугольник ABCD задан координатами своих...

Программа для нахождения площади данного четырехугольника
Дан произвольный выпуклый четырехугольник. Составить программу для нахождения...

Найти площадь произвольного четырехугольника, заданного координатами своих вершин
Помогите с задачкой пожалуйста 2. Найти площадь произвольного...

4
Sanya_sa
Модератор
708 / 692 / 301
Регистрация: 03.02.2015
Сообщений: 4,422
Записей в блоге: 8
Завершенные тесты: 3
17.02.2016, 01:42 2
pnt этих точек?

1) вариант
C#
1
2
3
4
for (int i = 0; i < pnt.Count; i++)
{
     var res = pnt[i];
}
2) вариант

C#
1
2
3
4
foreach(var point in pnt )
{
      point ; // это Ваша точка
}
0
Nike1995
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
17.02.2016, 02:34  [ТС] 3
нет, как построить все возможные четырехугольники, которые можно построить на мн-ве этих точек
0
Sanya_sa
Модератор
708 / 692 / 301
Регистрация: 03.02.2015
Сообщений: 4,422
Записей в блоге: 8
Завершенные тесты: 3
17.02.2016, 02:44 4
Цитата Сообщение от Nike1995 Посмотреть сообщение
нет, как построить все возможные четырехугольники, которые можно построить на мн-ве этих точек
Я в код не вникал - думал Вы все построили что нужно))) , Вопрос был как перебрать точки - вот я и ответил.
А как построить - это думать нужно до программирования тут еще далеко, с начало матеметически (геометрически) решите задачу, а код поможем написать.
0
Nike1995
3 / 3 / 8
Регистрация: 14.10.2012
Сообщений: 288
17.02.2016, 03:14  [ТС] 5
вся математика уже есть. определяется вид четырехугольника по 4м точкам, находится площадь треугольников. Единственное, что нужно- это перебрать все точки и это не математика, а программирование.
Предполагаю, что будет три-четыре вложенных цикла for но с индексами не могу разобраться.

Добавлено через 59 секунд
и вопрос был не как перебрать все точки, а как перебрать все четырехугольники.
0
17.02.2016, 03:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2016, 03:14

по введеным координатам вершин четырехугольника определить длины диагоналей и его площадь
по введеным координатам вершин четырехугольника определить длины диагоналей м...

Матрица по условиям
Мне нужно чтобы консольная программа на c# вывела все возможные матрицы...

Обмен столбцов матрицы по условиям
24. Дана матрица размера N×M. Поменять местами столбец с номером 11|M2 и...


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

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

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