デカルト平面の三角形の領域

Question

私はユーザ入力を行うプログラムを作ろうとしていますのxy座標のペアです。プログラムは、三角形の頂点として（0,0）から3つの最も遠い点を使用する必要があります。プログラムは、三角形の領域を出力する必要があります。私はそれのための数式を知っているが、私は（0,0）から3つの遠い点を得ることに問題があります。

ここでは、x座標のみを昇順でソートするコードがあります。どのようにペアを並べ替え、3つの最も遠いポイントを取得するのですか？ またはこのプログラムを作成するための良い方法はありますか？

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

次の2つの分離された変数を有するのではなく、座標を定義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; 
} 

あなたは3つの最も遠い点を見つけるのに役立ちます。

Answer 2

1つの方法は、それらの点のconvex hullを見つけることです。最も遠い点は、その凸包の頂点であり、頂点の最も遠い3点を取ることです。

Thisは、点集合の凸包を見つける方法の1つです。

また、thisにチェックを付けると、問題解決の方法を見つけるのに役立ちます。