Поиск четырехугольника удовлетворяющему условиям - 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 ; // это Ваша точка
- }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д