fzu_2148

参照先:https://blog.csdn.net/qq_32680617/article/details/51010533
題意:第1行はTを与えて、次にTグループのデータがあって、各グループのデータの第1行はNを与えて、次のN行、各行は1つの点のx,y座標を入力します.出力これらの点は全部でどれだけ凸四角形を構成することができますか.構想:凸包は判断しにくいが、凹包は判断しやすいだろう.もし4つの点a,b,c,dが凹包を構成し、a点が凹んでいれば、aと他の3つの点からなる三角形面積とb,c,dの3つの点からなる三角形面積に等しいと仮定する.自分で絵を描くと明らかだ.三角形の面積を取得する関数と、4つの三角形の面積関係を判断する関数を加えて、4層の循環暴力枚はすべての可能性を挙げます.考え方はとても良くて、細部の処理の上で、fabsで浮動小数点数の絶対値を取得して、1 e-6より小さいこのような方式の近似の判断で差の結果が0であるかどうかを判断して、浮動小数点数の演算は一般的に直接等しいかどうかを判定することはできないので、精度に関わって、正確ではありませんため、すべて近似の判断が等しいかどうかです.

#include 
#include 
using namespace std;
struct node{
    int x;
    int y;
};
node nodes[31];
double calculateS(node a,node b,node c)
{
    return fabs(1.0*(b.x-a.x)*(c.y-a.y)-1.0*(b.y-a.y)*(c.x-a.x))/2.0;
}
int is_tu(node a,node b,node c,node d)
{
    //  d     ,   0
    //                    ，            ，                  
    //                   0 
    if(fabs(calculateS(a,b,c)-calculateS(b,c,d)-calculateS(a,c,d)-calculateS(a,b,d))<1e-6)
        return 0;
    return 1;
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;++i)
    {
        int sum=0;
        int n;
        cin>>n;
        for(int j=0;j>x>>y;
            nodes[j].x=x;
            nodes[j].y=y;
        }
        for(int k=0;k