[2019HDU多校第四场][HDU 6617][D. Enveloping Convex]

题目链接：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}\)是能满足要求的。

巴特西

[2019HDU多校第四场][HDU 6617][D. Enveloping Convex]

最新文章

热门文章