Площадь треугольника в декартовой плоскости
Я пытаюсь сделать программу, которая делает пользовательский ввод пары координат ху. Программа должна использовать три самые дальние точки из (0,0) в качестве вершин треугольника. Программа должна вывести площадь треугольника. Я знаю формулу для этого, но у меня проблемы с получением трех самых дальних точек из (0,0).
Здесь у меня есть код для сортировки только координаты х в порядке возрастания. Как отсортировать пары и получить три самых дальних пункта?
Или есть ли лучший способ сделать эту программу?
int main() {
int x, a, b, t;
cin >> a; // a pairs of x and y
int xcoor[a], ycoor[a];
for (x = 1; x <= a; x++)
{
//enter coordinates
cin >> xcoor[x] >> ycoor[x];
}
for (x = 0; x < a; x++)
{
for (int y = 0; y < a - 1; y++)
{
if (xcoor[y] > xcoor[y + 1])
{
t = xcoor[y];
xcoor[y] = xcoor[y + 1];
xcoor[y + 1] = t;
}
}
}
return 0;
}
Решение
Один из способов — найти выпуклый корпус из этих точек самые дальние точки являются вершинами этого выпуклого корпуса, возьмите самые дальние 3 из вершин.
это это один из способов найти выпуклую оболочку множества точек.
Вы также можете проверить этот, это может помочь вам найти способ решения вашей проблемы.
Другие решения
Вы можете определить struct Point который определяет координату вместо двух разделенных переменных.
С operator< по точкам, выражающим расстояние от центра, вы можете использовать std::sort сортировать массивы / векторы Point,
Что-то вроде:
struct Point {
int x, y;
bool operator<(const Point& src) const
{ return x*x + y*y < src.x*src.x + src.y*src.y; // or anything else
}
};
int main() {
int x,a,b,t;
cin>>a; // a pairs of x and y
Point point[a]; // be careful, it is a gcc extension since a is not a compilation constant
for (x=0; x<a; x++) // be careful, arrays in C/C++ starts from 0!
{
//enter coordinates
cin>>point[x].x>>point[x].y;
}
std::sort(&point[0], &point[a]);
return 0;
}
поможет вам найти три самых дальних точек.