笛卡爾飛機中三角形的區域

Question

我正在嘗試製作一個程序，使用戶輸入a對xy座標。程序必須使用（0,0）中最遠的三個點作爲三角形的頂點。程序必須輸出三角形的區域。我知道它的公式，但我從（0,0）得到三個最遠點時遇到了麻煩。

在這裏，我有代碼僅按升序排序x座標。我如何對這些對進行排序並得到三個最遠的點？ 或者有沒有更好的方法來製作這個程序？

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; 
} 

Answer 1

可以定義一個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; 
} 

幫助您找到三個最遠點。

Answer 2

一種方法是找到這些點的convex hull，最遠點是該凸包的頂點，取最遠的3個頂點。

This是找到一組點的凸包的一種方法。

您還可以檢查this，它可能會幫助您找到解決問題的方法。