题目
给到\(N\) \((N{\le}50)\)个点，求两个不相交的凸包，使得其中面积较大的那个面积最小。
分析
比赛的时候还剩一个半小时写这个题，其实就是很简单的计算几何，但是因为一些原因想复杂了。这里还学到了向量叉积。 因为\(N\)很小，所以可以直接枚举两个点，作出一条直线，把点分到两边，直接计算即可。问题在于，这条直线上的点该放到哪边。场上分类讨论了一下，分组就写了近70行，其实不用这么麻烦。只要线上的点都放在同一边，所有情况都会枚举到。 现在问题是如何判断一个定点在一条给定直线的哪一边。使用向量叉积：\[ {\boldsymbol a}=(x\_a,y\_a), \boldsymbol b=(x\_b,y\_b) \\ \boldsymbol a \times \boldsymbol b=|\boldsymbol a|\*|\boldsymbol b|\*sin(\boldsymbol a,\boldsymbol b)=x \_ a \* y \_ b-x \_ b \* y \_a \] 向量公式与坐标公式可用\(sin\)的差角公式得到。 因此，若有两个向量\({\boldsymbol a}\)和\(\boldsymbol b\)，那么令\(\boldsymbol c=\boldsymbol a \times \boldsymbol b\)，若\(\boldsymbol c=0\)，则\(\boldsymbol a\)与\(\boldsymbol b\)在同一方向上。若\(\boldsymbol c<0\)，则\(\boldsymbol b\)在\(\boldsymbol a\)的顺时针方向上，\(\boldsymbol b\)在\(\boldsymbol a\)的逆时针方向上。同时，由：\[ S\_{\triangle ABC}={\frac {1}{2}} a \* b \* sinC \] 可得：\[ |{\boldsymbol a} {\times} {\boldsymbol b}|=2*S_{\triangle OAB} \] 可用向量叉积进行极角排序（以一个点建立极坐标按照顺时针或者逆时针编号）和计算三角形面积。
代码
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
typedef long double longd;
const int maxn=55;
const longd eps=1e-9;
struct node {
longd x,y;
bool operator == (const node a) const {
return x==a.x && y==a.y;
}
} a[maxn],lf[maxn],rt[maxn];
int ls,rs,ts,n;
inline bool byall(node a,node b) {
return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline longd sqr(longd x) {
return x*x;
}
inline longd dis(node a,node b) {
return sqrt(sqr(b.x-a.x)+sqr(b.y-a.y));
}
inline longd cross(node a,node b,node c) {
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
inline void where(int thea,int theb) {
node pa=a[thea],pb=a[theb];
for (int i=1;i<=n;++i) if (cross(pa,pb,a[i])>=0) lf[++ls]=a[i]; else rt[++rs]=a[i];
}
node sta[maxn];
node the;
inline bool angle(node a,node b) {
longd ji=cross(the,a,b);
if (ji==0) return dis(the,a)<dis(the,b);
return ji<0;
}
inline void pack(node t[],int <) {
int gs=0,top;
if (lt<2) return;
the.y=the.x=1e300;
int id=0;
for (int i=1;i<=lt;++i) if (t[i].x<the.x || (t[i].x==the.x && t[i].y<the.y)) the=t[i],id=i;
swap(t[1],t[id]);
sort(t+2,t+lt+1,angle);
top=0;
for (int i=1;i<=lt;++i) {
while (top>1 && cross(sta[top-1],sta[top],t[i])>=0) --top;
sta[++top]=t[i];
}
lt=top;
for (int i=1;i<=lt;++i) t[i]=sta[i];
}
inline longd size(node t[],int lt) {
longd ret=0;
node da=t[1];
for (int i=2;i<lt;++i) ret+=cross(t[1],t[i+1],t[i])/2;
return ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%Lf%Lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,byall);
n=unique(a+1,a+n+1)-a-1;
if (n<=4) printf("%.6Lf\n",(longd)0.0),exit(0);
longd ans=1e300,sa,sb;
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) {
ls=0,rs=0;
memset(lf,0,sizeof lf),memset(rt,0,sizeof rt);
where(i,j);
pack(lf,ls);
pack(rt,rs);
sa=size(lf,ls);
sb=size(rt,rs);
ans=min(ans,max(sa,sb));
}
printf("%.6Lf\n",ans);
}
转载于:https://www.cnblogs.com/owenyu/p/6724747.html
相关资源：灵璧县公路巡逻队工作调研报告.doc
