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

Узнай цену своей работы

Формулировка задачи:

Задание: даны мн-во точек, найти выпуклый четырехугольник, такой, что разность площадей наименьшего и наибольшего треугольников(образованного диагоналями четырехугольника), минимальна. Все вроде сделал, только не знаю как перебрать все четырехугольники на мн-ве точек!
Листинг программы
  1. using System;
  2. using System.Collections.Generic;
  3. using System.ComponentModel;
  4. using System.Data;
  5. using System.Drawing;
  6. using System.Linq;
  7. using System.Text;
  8. using System.Windows.Forms;
  9. namespace WindowsFormsApplication2
  10. {
  11. public partial class Form1 : Form
  12. {
  13. public int x, y;
  14. List<PointF> pnt = new List<PointF>();
  15. public float n, nx, ny;
  16. public String s;
  17. public int p = 0;
  18. float cos;
  19. bool key = true;
  20. float x_c, y_c;
  21. PointF ab, ao;
  22. float sum;
  23. public Form1()
  24. {
  25. InitializeComponent();
  26. }
  27. //вырисовываем точки
  28. private void ttt(float x, float y)
  29. {
  30. Pen MyPen = new Pen(Color.Black, 3);
  31. Graphics g = Graphics.FromHwnd(pictureBox1.Handle);
  32. g.DrawEllipse(MyPen, x - 5, y - 5, 10, 10);
  33. }
  34. // находим угол между векторами
  35. private float get_ugol(float a_x, float a_y, float b_x, float b_y,
  36. float c_x, float c_y)
  37. {
  38. float s_x = 0, s_y = 0, t_x = 0, t_y = 0;
  39. s_x = b_x - a_x;
  40. s_y = b_y - a_y;
  41. t_x = c_x - a_x;
  42. t_y= c_y - a_y;
  43. float Pr_1 = s_x * t_x + s_y * t_y;
  44. double sqr1 = Math.Sqrt(s_x * s_x + s_y * s_y);
  45. double sqr2 = Math.Sqrt(t_x * t_x + t_y* t_y);
  46. cos = Pr_1 / ((float)sqr1 * (float)sqr2);
  47. return cos;
  48. }
  49. // считает площадь треугольника
  50. private float get_area(float x_1, float y_1, float x_2, float y_2, float x_3, float y_3)
  51. {
  52. float a_b, a_o;
  53. float sin, buf;
  54. ab.X = x_2 - x_1;
  55. ab.Y = y_2 - y_1;
  56. ao.X = x_3 - x_1;
  57. ao.Y = y_3 - y_1;
  58. a_b = (float)Math.Sqrt((double)(ab.X * ab.X) + (double)(ab.Y * ab.Y));
  59. a_o = (float)Math.Sqrt((double)(ao.X * ao.X) + (double)(ao.Y * ao.Y));
  60. buf = get_ugol(x_1, y_1, x_2, y_2, x_3, y_3);
  61. sin = (float)Math.Sqrt(1 - (double)(buf * buf));
  62. sum = (float)(a_b * a_o * sin) / 2;
  63. return sum;
  64. }
  65. // добавление точек в список
  66. private void button1_Click(object sender, EventArgs e)
  67. {
  68. PointF p1 = new PointF();
  69. p1.X = (float)numericUpDown1.Value;
  70. p1.Y = (float)numericUpDown2.Value;
  71. pnt.Add(p1);
  72. n = pnt.Count();
  73. for (int i = p; i < n; i++)
  74. {
  75. nx = pnt[i].X;
  76. ny = pnt[i].Y;
  77. s = (p+1) + " " + nx.ToString() + " " + ny.ToString();
  78. listBox1.Items.Add(s);
  79. s = "";
  80. ttt(nx, ny);
  81. }
  82. p++;
  83. }
  84. // является ли четырехугольник вырожденным
  85. private bool is_convex(int i, int j, int k, int z)
  86. {
  87. double eps = 0.1;
  88. float c_1, c_2, c_3, c_4;
  89. double sum;
  90. c_1 = get_ugol(pnt[i].X, pnt[i].Y, pnt[j].X, pnt[j].Y, pnt[z].X, pnt[z].Y);
  91. c_2 = get_ugol(pnt[j].X, pnt[j].Y, pnt[i].X, pnt[i].Y, pnt[k].X, pnt[k].Y);
  92. c_3 = get_ugol(pnt[k].X, pnt[k].Y, pnt[j].X, pnt[j].Y, pnt[z].X, pnt[z].Y);
  93. c_4 = get_ugol(pnt[z].X, pnt[z].Y, pnt[k].X, pnt[k].Y, pnt[i].X, pnt[i].Y);
  94. sum = Math.Acos(c_1) * 180 / Math.PI + Math.Acos(c_2) * 180 / Math.PI +
  95. Math.Acos(c_3) * 180 / Math.PI + Math.Acos(c_4) * 180 / Math.PI;
  96. if (360 - sum > eps)
  97. {
  98. key = false;
  99. return key;
  100. }
  101. return key;
  102. }
  103. // поиск координат центра четырехугольника(пересечение диагоналей)
  104. private void centre(float x_1, float y_1, float x_2, float y_2,
  105. float x_3, float y_3, float x_4, float y_4)
  106. {
  107. 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))/
  108. ((x_2-x_1)/(y_2-y_1)*(y_4-y_3)-(x_4-x_3));
  109. x_c = y_c*(x_2-x_1)/(y_2-y_1)-y_1*(x_2-x_1)/(y_2 - y_1)+x_1;
  110. }
  111. //поиск выпуклого четырехугольника
  112. private void button2_Click(object sender, EventArgs e)
  113. {
  114. float sum;
  115. bool g = is_convex(0,1,2,3);
  116. if (g) MessageBox.Show("Выпуклый");
  117. else MessageBox.Show("Вогнутый");
  118. 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);
  119. sum = get_area(pnt[0].X, pnt[0].Y, pnt[1].X, pnt[1].Y, x_c, y_c);
  120. //здесь должен быть перебор точек
  121. }
  122. }
  123. }

Решение задачи: «Поиск четырехугольника удовлетворяющему условиям»

textual
Листинг программы
  1. foreach(var point in pnt )
  2. {
  3.       point ; // это Ваша точка
  4. }

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


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

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

14   голосов , оценка 4 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы