注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1027  

2013-02-05 13:13:57|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

注:bzoj 1032祖玛一题数据有误,标程有误

bzoj1027合金:

这道题的方法真的好神奇,我觉得简直是闻所未闻啊!

对于一个东西,他有三个量。但事实上,由于和一定,所以两个量即可表示,那么可以把合金和材料抽象为平面直角坐标系上的点。

然后,对于两个材料,他们能合成的合金就是以两个点为端点的线段上的点。

简单的证明一下:

首先证明三点共线上,大致就是把线段AB上某个点P表达式写出来,之后再用叉积发现PA X PB = 0

然后证明在两端点之间,这很显然……

这样的话,如果n个材料点构成的凸包囊括了所有合金点,就必然可行,因为一个合金点可以看作是某两个在凸包边上的点构成的线段上的点……

所以,思路就是说,如果m个材料点能够成一个凸多边形且包括了所有合金点,m便可行。最小的m就是答案。

那么怎么求最小的m呢??

竟然是图论!

如果所有合金点在某两个材料点的有向线段,那么连一条有向边,最小环即为所求!

最小环算法我是在usaco上学到的,有向图最小环就是Floyd后的min{F[i][i]}

总结:这道题用上了数形结合+图论!!神奇啊

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 510
#define eps 1e-15
using namespace std;
int dcmp(double p)
{
    if(fabs(p)<eps)  return 0;
    return p>eps?1:-1;
}
struct Point
{
    double x,y;
    Point() {}
    Point(double x,double y): x(x),y(y) {}
    friend Point operator - (const Point &a,const Point &b){  return Point(a.x-b.x,a.y-b.y);  }
    friend bool operator != (const Point &a,const Point &b){  return dcmp(a.x-b.x)||dcmp(a.y-b.y);  }
    friend bool operator < (const Point &a,const Point &b){  return dcmp(a.x-b.x)<0||(!!dcmp(a.x-b.x)&&dcmp(a.y-b.y)<0);  }
}data[MAXN],metal[MAXN];
typedef Point Vector;
double Cross(const Vector &a,const Vector &b){  return a.x*b.y-a.y*b.x;  }
bool Left(const Point &a,const Point &b,const Vector &c){  return dcmp(Cross(c,a-b))>0;  }
bool On(const Point &a,const Point &b,const Point &c){  return !dcmp(Cross(b-a,c-a))&&dcmp((a.x-b.x)*(a.x-c.x))<=0&&dcmp((a.y-b.y)*(a.y-c.y))<=0;  }
int F[MAXN][MAXN],len[MAXN][MAXN],n,m;
void read()
{
    scanf("%d %d",&n,&m);
    double a,b,c;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf %lf",&a,&b,&c);
        data[i]=Point(a,b);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lf %lf %lf",&a,&b,&c);
        metal[i]=Point(a,b);
    }
}
void make_graph()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            len[i][j]=1<<29;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int dis=1;
            for(int k=1;k<=m&&dis==1;k++)
                if(!Left(metal[k],data[i],data[j]-data[i])&&!On(metal[k],data[i],data[j]))
                    dis=1<<29;
            len[i][j]=dis;
        }
}
int Floyd()
{
    for(int i=1;i<=n;i++)
    {
        bool mark=true;
        for(int j=1;j<=m&&mark;j++)
            if(data[i]!=metal[j])
                mark=false;
        if(mark)  return 1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            bool mark=true;
            for(int k=1;k<=m&&mark;k++)
                if(!On(metal[k],data[i],data[j]))
                    mark=false;
            if(mark)  return 2;
        }
    int ans=1<<29;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            F[i][j]=len[i][j];
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                F[i][j]=min(F[i][j],F[i][k]+F[k][j]);
    for(int i=1;i<=n;i++)
        ans=min(ans,F[i][i]);
    return ans==1<<29?-1:ans;
}
int main()
{
    read();
    make_graph();
    printf("%d\n",Floyd());
    return 0;
}



  评论这张
 
阅读(691)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017