【bzoj1027】[JSOI2007]合金

2015.04.22 12:26 Wed | 4次阅读 | 旧日oi | 固定链接 | 源码

Description

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。

Input

第一行两个整数m和n(m, n ≤ 500),分别表示原材料种数和用户需要的合金种数。第2到m + 1行,每行三个实数a, b, c(a, b, c ≥ 0 且 a + b + c = 1),分别表示铁铝锡在一种原材料中所占的比重。第m + 2到m + n + 1行,每行三个实数a, b, c(a, b, c ≥ 0 且 a + b + c = 1),分别表示铁铝锡在一种用户需要的合金中所占的比重。

Output

一个整数,表示最少需要的原材料种数。若无解,则输出–1。

Sample Input

10 10
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0

Sample Output

5

题解

看了题解之后,发现这的确是一道好题……
我们可以把三维的状态压成两维,因为如果有两维相等,那么第三维也一定相等。
于是我们可以把每种合金看成二位平面上的一个点,那么两中合金能组合出来的材料就在这两个点连接的线段上,进而,n种合金能合成的材料就在这n个点围成的凸包里。
我们要找的就是覆盖了所有目标点的一个环,用找环可以用Floyd,那么怎么建图?
任选两个点,如果所有的目标点都在这两个点所构成的线段的一侧,就连一条有向边,用叉积判断一下就行。
特殊情况:
1.所有点都重合,此时ans=1
2.所有目标点在某两个点之间的线段上,此时ans=2
3.所有目标点在某两个点所确定的直线上,此时建双向边,因为有可能答案是一条直线状的

我的程序

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define eps 1e-10
int n,m;
struct Point
{
    double x,y;
}a[505],b[505];
Point operator -(Point a,Point b)
{
    Point c;
    c.x=a.x-b.x;
    c.y=a.y-b.y;
    return c;
}
double cross(Point x,Point y)
{
    return x.x*y.y-x.y*y.x;
}
int dis[505][505];
bool judge(int x,int y)
{
    Point t1=a[x],t2=a[y];
    if(t1.x>t2.x) swap(t1.x,t2.x);
    if(t1.y>t2.y) swap(t1.y,t2.y);
    for(int i=1;i<=m;i++)
        if(b[i].x<t1.x||b[i].x>t2.x) return 0;
    for(int i=1;i<=m;i++)
        if(b[i].y<t1.y||b[i].y>t2.y) return 0;
    return 1;
}
void link(int x,int y)
{
    int c1=0,c2=0;
    for(int i=1;i<=m;i++)
    {
        if(cross(a[y]-a[x],b[i]-a[x])>eps) c1++;
        else if(cross(a[y]-a[x],b[i]-a[x])<-eps) c2++;
        if(c1*c2) return;
    }
    if(!(c1+c2)&&judge(x,y))
    {
        puts("2");
        exit(0);
    }
    if(c1) dis[x][y]=1;
    else if(c2) dis[y][x]=1;
    else dis[x][y]=dis[y][x]=1;
}
void work()
{
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            link(i,j);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    int ans=inf;
    for(int i=1;i<=n;i++) ans=min(ans,dis[i][i]);
    if(ans<=2||ans==inf) puts("-1");
    else cout<<ans<<endl;
}
bool check()
{
    for(int i=2;i<=n;i++)
        if(fabs(a[i].x-a[i-1].x)>eps||fabs(a[i].y-a[i-1].y)>eps) return 0;
    for(int i=1;i<=m;i++)
        if(fabs(b[i].x-a[i].x)>eps||fabs(b[i].y-a[i].y)>eps) return 0;
    puts("1");
    return 1;
}
int main()
{
    //freopen("1027.in","r",stdin);
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lf%lf%*lf",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf%*lf",&b[i].x,&b[i].y);
    if(check()) return 0;
    work();
    return 0;
}```