#include "stdio.h"
#include "math.h"
struct point
{
int x;
int y;
};
void main()
{
int n,i,p,x,y,x0,y0,t,num;
struct point a[106],s[106],temp;
float tem[106];
double area;
void sort(float p[],struct point a[],int start,int end);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
if (n<=2)
{
area=0;
}
else
{
x0=x=a[0].x;
y0=y=a[0].y;
p=1;
for(i=1;i<n;i++)
{
if(x>a[i].x ||(x==a[i].x && y<a[i].y))
{
x=a[i].x;
y=a[i].y;
p=i;
}
}
a[0].x=x;
a[0].y=y;
a[p].x=x0;
a[p].y=y0;
for(i=1;i<n;i++)
{
if(a[i].x-a[0].x==0)
tem[i]=-9990;
else
tem[i]=100*(a[i].y-a[0].y)/(a[i].x-a[0].x);
}
sort(tem,a,1,n-1);
s[0]=a[0];
s[1]=a[1];
s[2]=a[2];
num=2;
for(i=3;i<n;i++)
{
while(num>0)
{
temp=s[num];
num--;
p=s[num].x*temp.y+a[i].x*s[num].y+temp.x*a[i].y-a[i].x*temp.y-temp.x*s[num].y-s[num].x*a[i].y;
if(p>0)
{
num++;
s[num]=temp;
break;
}
}
num++;
s[num]=a[i];
}
area=0;
temp=s[num];
num--;
area+=(a[0].x*temp.y-a[0].y*temp.x)/2.0;
while(num>-1)
{
area+=(temp.x*s[num].y-temp.y*s[num].x)/2.0;
temp=s[num];
num--;
}
if(area<0)
area=-area;
}
printf("%.1f\n",area);
}
}
void sort(float p[],struct point *a,int start,int end)
{
int i=start,j=end;
float tmp;
struct point b;
if(start<end)
{
tmp=p[start];
b=a[start];
while(i!=j)
{
while(j>i && p[j]>=tmp)
j--;
p[i]=p[j];
a[i]=a[j];
while(i<j && p[i]<=tmp)
i++;
p[j]=p[i];
a[j]=a[i];
}
p[i]=tmp;
a[i]=b;
sort(p,a,start,i-1);
sort(p,a,j+1,end);
}
}
评论0