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