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

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4 из 5
Похожие ответы