
题意:给出笛卡尔坐标系上 n 个点,n不大于100,求出这些点中能围出的最小面积。
可以肯定的是三个点围成的面积是最小的,然后就暴力枚举,计算任意三点围成的面积。刚开始是求出三边的长,然后求面积,运算步骤多,超时鸟~~,后来看了别人的代码,计算步骤挺少啊,不过我不会推这个式子。
#include<stdio.h>
#include<string.h>
#include<math.h> struct node{
double x,y;
};
node point[];
const double inf = ; double Deal(node a,node b,node c)
{
return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x - a.x))/;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
double ans=inf;
bool flag=false;
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%lf%lf",&point[i].x,&point[i].y);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
if(j!=i)
for(int k=;k<n;k++)
if(k!=j && k!=i)
{
double tmp=Deal(point[i],point[j],point[k]);
if(tmp<) tmp=-tmp;
if(tmp < ans && tmp != 0.0)
{
ans = tmp;
flag = true;
}
}
if(flag) printf("%.2lf\n",ans);
else printf("Impossible\n");
}
return ;
}