题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6617
题目大意：给出一凸包\(P\)，求最小的与\(P\)相似且对应边平行的多边形，使得题目给出的\(m\)个点\(q_i\)都被该多边形包含在内，输出最小相似比
题解：二分答案\(k\)，考虑如何判断\(P\)被放大\(k\)倍后是否可以通过平移这\(m\)个点使他们都在多边形内。将多边形的所有边看成有向线段（逆时针），则\(m\)个点都在多边形内当且仅当他们都在这些有向线段的左侧。对第\(i\)条边记录\(f_i\)表示如果点\(q_{f_i}\)在这条边左侧，就能保证所有点都在其左侧，通过对这\(m\)个点求凸包后可以在\(O(m)\)的时间复杂度内求出\(f_i\)。这样我们就只需要知道，是否存在一个平移的向量，使得这\(m\)个点平移之后，所有的点\(q_{f_i}\)都在第\(i\)条边的左侧。
于是我们如果对每条边\((p_i,p_{i+1})\)，求出了符合条件的向量集\(\vec{A_i}\)，就可以通过判断他们的交集是否为空来判断当前的比例\(k\)是否合法。可以发现\(\vec{A_i}=\{\vec{OA}|A\text{ is on the left of }\vec{(p_i-q_{f_i},p_{i+1}-q_{f_i})}\}\)代表了一个半平面，这时我们就可以通过求半平面交来解决这道题了。
注意题目的要求是对应边平行，因此我们还要把原图形旋转\(180^{\circ}\)再做一遍，取两次答案的最小值输出。
#include<bits/stdc++.h>
using namespace std;
#define N 100001
const double eps=1e-;
int sgn(double x)
{
if(x<-eps)return -;
if(x>eps)return ;
return ;
}
struct Point
{
double x,y;
void read(){scanf("%lf%lf",&x,&y);}
Point operator +(const Point &t)const{return {x+t.x,y+t.y};}
Point operator -(const Point &t)const{return {x-t.x,y-t.y};}
double operator *(const Point &t)const{return x*t.y-y*t.x;}
Point operator *(const double t)const{return {x*t,y*t};}
Point operator /(const double t)const{return {x/t,y/t};}
double ang()const{return atan2(1.0*y,1.0*x);}
double length()const{return sqrt(x*x+y*y);}
}p[N];
struct Line
{
Point p1,p2;
Point isct(const Line &t)const
{
double a=(p2-p1)*(t.p1-p1);
double b=(p2-p1)*(p1-t.p2);
return (t.p1*b+t.p2*a)/(a+b);
}
}q[N],line[N];
Point cent;
bool cmpang(const Point &p1,const Point &p2)
{
int tmp=sgn((p1-cent).ang()-(p2-cent).ang());
if(tmp!=)return tmp<;
return (p1-cent).length()<(p2-cent).length();
}
struct Polygon
{
int n;
Point a[N];
void read()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
a[i].read();
}
void ChangetoConvex()
{
for(int i=;i<=n;i++)
if(a[i].x<a[].x || (a[i].x==a[].x && a[i].y<a[].y))
swap(a[],a[i]);
cent=a[];
sort(a+,a+n+,cmpang);
int top=;
for(int i=;i<=n;i++)
{
while(top>= && (a[top]-a[top-])*(a[i]-a[top])<=)top--;
a[++top]=a[i];
}
n=top;
}
}P,Q;
int T,nxt[N],pre[N],f[N];
bool check(int i,Point A,Point B)
{
return sgn((B-A)*(Q.a[pre[i]]-Q.a[i]))>= && sgn((B-A)*(Q.a[nxt[i]]-Q.a[i]))>=;
}
bool Left(const Point &p,const Line &l){return sgn((l.p2-l.p1)*(p-l.p1))==;}
bool HalfPlane(int n)
{
int h=,t=;
q[]=line[];
for(int i=;i<=n;i++)
{
while(h<t && !Left(p[t-],line[i]))t--;
while(h<t && !Left(p[h],line[i]))h++;
if(sgn((q[t].p2-q[t].p1)*(line[i].p2-line[i].p1))==)
q[t]=Left(q[t].p1,line[i])?q[t]:line[i];
else q[++t]=line[i];
if(h<t)p[t-]=q[t].isct(q[t-]);
}
while(h<t && !Left(p[t-],q[h]))t--;
if(t-h<=)return false;
p[t]=q[t].isct(q[h]);
double ans=;
for(int i=h;i<=t;i++)
ans+=p[i]*p[(i+-h)%(t-h+)+h];
return sgn(ans)>=;
}
bool check(double k)
{
for(int i=;i<=P.n;i++)
line[i]={P.a[i]*k-Q.a[f[i]],P.a[i%P.n+]*k-Q.a[f[i]]};
return HalfPlane(P.n);
}
double solve()
{
int j=;
for(int i=;i<=P.n;i++)
{
while(!check(j,P.a[i],P.a[i%P.n+]))j=nxt[j];
f[i]=j;
}
double l=,r=1e9,mid;
while(l+eps<r)
{
mid=(l+r)*0.5;
if(check(mid))r=mid;
else l=mid;
}
return l;
}
void init()
{
double ans=1e18;
P.read(),Q.read();
if(Q.n==){printf("%.6f\n",0.0);return;}
P.ChangetoConvex();
Q.ChangetoConvex();
for(int i=;i<=Q.n;i++)
nxt[i]=i%Q.n+,pre[i%Q.n+]=i;
ans=min(ans,solve());
for(int i=;i<=P.n;i++)
P.a[i]=P.a[i]*(-1.0);
ans=min(ans,solve());
printf("%.6f\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)init();
}
关于\(\vec{A_i}\)的说明：设点\(q_{f_i}\)为\(Q\)，则\(\vec{OA}\)满足原点\(O\)在平移\(\vec{OA}\)后，他在有向线段\(\vec{(p_i-Q,p_{i+1}-Q)}\)的左侧。所以原点\(O\)在平移\(\vec{OA}\)后，再平移\(\vec{OQ}\)，就能满足其在有向线段\(\vec{(p_i,p_{i+1})}\)的左侧。而\(O+\vec{OA}+\vec{OQ}=O+\vec{OQ}+\vec{OA}=Q+\vec{OA}\)，因此将\(Q\)平移\(\vec{OA}\)是能满足要求的。