bzoj 1027: [JSOI2007]合金【凸包+Floyd】

参考：https://www.cnblogs.com/zhuohan123/p/3237246.html

因为一c可以由1-a-b得出，所以删掉c，把a，b抽象成二维平面上的点。首先考虑一个客户需求能被哪些原料配出来：两个原料点连线上的点都可以，要是多个原料点，那么这些线的向量构成的凸包中的点都可以

所以得到了一个n三方算法：枚举每两个原料点，看是否所有需求点都在这条向量的半平面里，是则连1，然后Floyd求最小环即可

但是有非常多恶心的特判……

1.需求点重合为一点

2.需求点出现在两种原料点所在直线上的情况

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=505,inf=1e9;

const double eps=1e-10;

int m,n,a[N][N];

double c;

struct dian

{

    double x,y;

    dian(double X=0,double Y=0)

	{

        x=X,y=Y;

	}

	dian operator - (const dian &a) const

	{

		return dian(x-a.x,y-a.y);

	}

}q[510],p[510];

dian V(dian a,dian b)

{

	return dian(b.x-a.x,b.y-a.y);

}

double cj(dian a,dian b)

{

	return a.x*b.y-b.x*a.y;

}

bool ok(dian s,dian t,dian p)

{

    return !((s.x>p.x&&t.x>p.x)||(s.x<p.x&&t.x<p.x)||(s.y>p.y&&t.y>p.y)||(s.y<p.y&&t.y<p.y));

}

int main()

{

    scanf("%d%d",&m,&n);

    for(int i=1;i<=m;i++)

	    scanf("%lf%lf%lf",&p[i].x,&p[i].y,&c);

    for(int i=1;i<=n;i++)

	    scanf("%lf%lf%lf",&q[i].x,&q[i].y,&c);

    for(int i=1;i<=m;i++)

    {

        bool flag=1;

        for(int j=1;j<=n;j++)

            if(abs(p[i].x-q[j].x)>eps||abs(p[i].y-q[j].y)>eps)

                flag=0;

        if(flag)

		{

		    printf("1\n");

			return 0;

		}

    }

    for(int i=1;i<=m;i++)

        for(int j=1;j<=m;j++)

            a[i][j]=inf;

    for(int i=1;i<=m;i++)

        for(int j=1;j<=m;j++)

        if(i!=j)

        {

            if(abs(p[i].x-p[j].x)<eps&&abs(p[i].y-p[j].y)<eps)

			    continue ;

            int can=1;

            for(int k=1;k<=n;k++)

                if(cj(p[j]-p[i],q[k]-p[i])<-eps)

				    can=0;

            if(can)

            {

                for(int k=1;k<=n;k++)

                {

                    double cp=cj(p[j]-p[i],q[k]-p[i]);

                    if(cp<eps&&cp>-eps&&(!ok(p[i],p[j],q[k])))

					    can=0;

                }

            }

            if(can)

			    a[i][j]=1;

        }

    int ans=inf;

    for(int k=1;k<=m;k++)

        for(int i=1;i<=m;i++)

            for(int j=1;j<=m;j++)

                if(a[i][j]>a[i][k]+a[k][j])

                    a[i][j]=a[i][k]+a[k][j];

    for(int i=1;i<=m;i++)

        for(int j=1;j<=m;j++)

        {

            if(i!=j&&a[i][j]+a[j][i]<ans)

			    ans=a[i][j]+a[j][i];

            if(i==j&&a[i][j]<ans)

			    ans=a[i][j];

        }

    printf("%d\n",ans==inf?-1:ans);

    return 0;

}

巴特西

bzoj 1027: [JSOI2007]合金【凸包+Floyd】

最新文章

热门文章