题解：LGOJT4534 [CTSC2004]最优切割

· · 题解

由于不懂得上传图床，本题解没有图，看图可以移步这篇题解。（不是我写的）

先考虑无共线情况的答案，注意到零件上的每条边都必须切，此外，每条边延伸与外多边形交出交点，每个顶点相邻两条边在这个顶点上的延伸线至少要选一条，考虑如果每个节点都是选同一方向的延伸线，这样子是不能切的，因此可以枚举哪个顶点放出了两条用来切的线段，剩下顶点去取两侧线段最小值。

考虑共线，容易发现如果共线则只需要排除零件上的该边即可，两侧相邻线段自动能将这边的距离取成 0，然后不去取那个长的线段，枚举哪个顶点放出了两条用来切的线段定能取到答案。

考虑如何寻找线段两侧与外延凸包的距离，使用双指针扫描即可。

注意要点：线段求交算距离，eps 要设为 1e-3，因为数据精度很差，比较靠近就算作共线了，不然零件有些顶点会在外面 1e-7 的位置，或者多算上了不共线部分导致答案过大。

是本题 AC 代码中唯二不使用特判的（时间复杂度 \Theta(n)），代码如下。

#include<cstdio>
#include<cmath>
const int N=2007;
typedef double ld;
const ld eps=5e-3;
struct pii{ld x,y;};
int sgn(ld x){return -eps<=x&&x<=eps?0:(x>0?1:-1);}
pii operator-(pii a,pii b){return {a.x-b.x,a.y-b.y};}
ld operator*(pii a,pii b){return a.x*b.y-a.y*b.x;}
ld gk(pii x){return x.y/x.x;}
ld min(ld a,ld b){return a<b?a:b;}
ld dis(pii x){return sqrt(x.x*x.x+x.y*x.y);}
int ups(pii x,pii a,pii b){return sgn((x-a)*(x-b));}
pii p[N],q[N];
ld a[N],b[N],f[N];int n,m;
ld deal(pii a,pii b,pii c,pii d)
{
    ld k=gk(a-b),K=gk(c-d);
    if(std::isinf(k)&&std::isinf(K))return 0;
    if(std::isinf(k))
    {
        ld p=(b.x-c.x)/(d.x-c.x);
        pii r={c.x+p*(d.x-c.x),c.y+p*(d.y-c.y)};
        return dis(r-b);
    }
    if(std::isinf(K))
    {
        ld p=(c.x-a.x)/(b.x-a.x);
        pii r={a.x+p*(b.x-a.x),a.y+p*(b.y-a.y)};
        return dis(r-b);
    }
    ld B1=a.y-k*a.x,B2=c.y-K*c.x;
    if(k==K)return 0;
    pii r={(B2-B1)/(k-K),0};r.y=k*r.x+B1;
    return dis(r-b);
}
int main()
{
    int s,t;ld ans=1e18,sum=0;
    scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
    scanf("%d",&m);for(int i=1;i<=m;++i)scanf("%lf%lf",&q[i].x,&q[i].y);
    for(int i=1;i<=n;++i)
    {
        int a=ups(p[i],q[1],q[2]),b=ups(p[i%n+1],q[1],q[2]);
        if(a>0&&b<=0)s=i;if(a<=0&&b>0)t=i;
    }
    for(int i=1;i<=m;++i)
    {
        while(ups(p[s%n+1],q[i],q[i%m+1])>0)s=s%n+1;
        while(ups(p[t%n+1],q[i],q[i%m+1])<=0)t=t%n+1;
        a[i]=deal(q[i%m+1],q[i],p[s],p[s%n+1]);
        b[i]=deal(q[i],q[i%m+1],p[t],p[t%n+1]);
        if(ups(p[s%n+1],q[i],q[i%m+1])||ups(p[t],q[i],q[i%m+1])||(s+1)%n+1!=t)sum+=dis(q[i]-q[i%m+1]);
    }
    for(int i=1;i<=m;++i)f[i]=f[i-1]+min(b[i],a[i%m+1]);
    for(int i=1;i<=m;++i)
        ans=min(ans,a[i]+b[i]+(i==1?f[m-1]:f[m]+f[i-2])-f[i]);
    printf("%.0lf",ans+sum);
    return 0;
}