题意:给出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("Impossible\n");
else
printf("%.2lf\n", minn);
}
}