【Herding HDU – 4709 】【数学（利用叉乘计算三角形面积）】

• 2019 年 10 月 10 日
• 筆記

题意：给出n个点的坐标，问取出其中任意点围成的区域的最小值！ 很明显，找到一个合适的三角形即可。

#include<iostream>  #include<cstdio>  #include<cstring>  #include<cmath>  #include<cstdlib>  #include<algorithm>  using namespace std;  const int maxn = 100 + 10;  const int INF = 0x3f3f3f3f;  int T, N;  struct Point  {      double _x, _y;  }p[maxn];  double Cross(int A, int B, int C)  {      double ABx = p[B]._x - p[A]._x;      double ABy = p[B]._y - p[A]._y;      double ACx = p[C]._x - p[A]._x;      double ACy = p[C]._y - p[A]._y;      return fabs(ABx*ACy - ABy*ACx) / 2.0;  }  int main()  {      // freopen("input.txt", "r", stdin);      // freopen("output.txt", "w", stdout);      scanf("%d", &T);      while(T--)      {          scanf("%d", &N);          for(int i = 0; i < N; i++)              scanf("%lf %lf", &p[i]._x, &p[i]._y);          double minn = INF;          for(int i = 0; i < N; i++)              for(int j = i + 1; j < N; j++)                  for(int k = j + 1; k < N; k++)                  {                      double s = Cross(i, j, k);                      if(s <= 1e-7)                          continue;                      minn = min(minn, s);                  }          if(fabs(minn - INF) < 1e-6)              printf("Impossiblen");          else              printf("%.2lfn", minn);      }  }