Поиск четырехугольника удовлетворяющему условиям - C#
Формулировка задачи:
Задание: даны мн-во точек, найти выпуклый четырехугольник, такой, что разность площадей наименьшего и наибольшего треугольников(образованного диагоналями четырехугольника), минимальна.
Все вроде сделал, только не знаю как перебрать все четырехугольники на мн-ве точек!
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); //здесь должен быть перебор точек } } }
Решение задачи: «Поиск четырехугольника удовлетворяющему условиям»
textual
Листинг программы
foreach(var point in pnt ) { point ; // это Ваша точка }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д