題意：
給你n個點，m個雷
找一個多邊形，使得多邊形的面積除以這個多邊形內雷的個數的比值最小
仔細想想，其實就是找一個比值最小的三角形就OK了，因為其他的三角形的比值都比它大，組合成多邊形後勢必會將比值變大
所以可以直接暴力O(n^3)枚舉三角形，再計算三角形內的雷的個數求比值即可
雷得個數的話預處理一個數組吧，畫張圖就懂了
cnt= （i k上方的點 ）- （ i j上方的點 + j k上方的點）
當然還要取絕對值
[cpp]
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct Point {
int x,y;
bool operator < (const Point &cmp) const{
return x<cmp.x;
}
}p[210],mine[510];
inline int XX(Point a,Point b,Point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int n,m;
int num[210][510];
void gao(Point a,Point b,int &cnt)
{
int x1=a.x,x2=b.x;
for(int i=0;i<m;i++) if(x1<=mine[i].x && mine[i].x<x2)//注意邊界，一邊是開區間
if(XX(a,b,mine[i])>0)
cnt++;
}
int main()
{
int t,ca=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
sort(p,p+n);
for(int i=0;i<m;i++) scanf("%d%d",&mine[i].x,&mine[i].y);
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) gao(p[i],p[j],num[i][j]=0);
double ans=-1;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)for(int k=j+1;k<n;k++)
{
int cnt=num[i][k]-num[i][j]-num[j][k];
if(cnt==0) continue;
double area=(double)XX(p[i],p[j],p[k])/2;
if(ans==-1 || fabs(area/cnt)<ans) ans=fabs(area/cnt);
}
if(ans!=-1) printf("Case #%d: %.6lf\n",ca++,ans);
else printf("Case #%d: -1\n",ca++);
}
return 0;
}
