bzoj1027【JSOI2007】合金

时间:2023-01-14 15:33:41

题目描述

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


输入格式

  第一行两个整数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),分别表示铁铝锡在一种用户需要的合金中
所占的比重。


输出格式

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


  • 题解

    • $a+b+c=1$所以忽略$c$,根据定比分点原则两个点可以表示的点组成它们连线段,推广一下;
    • 所以对$n$个点求出凸包,问题即用$m$个点去圈住凸包求最小点数;
    • 对两个材料$i,j$,如果凸包上的点都在连线$\vec{ij}$的左边就$i$向$j$连边,$floyd$求所有$dis[i][i]$即可;
    • 特判:
    • 当凸包是一个点时特判;
    • 当凸包是一条直线时,如果叉积为$0$还需要盖住所有点才可以加边,用点积特判;
    •  #include<bits/stdc++.h>
      #define db double
      #define inf 0x3f3f3f3f
      #define il inline
      #define eps 1e-7
      using namespace std;
      const int N=;
      int n,m,top,dis[N][N];
      il int dcmp(db x){return fabs(x)<eps?:x<?-:;}
      struct poi{
      db x,y;
      poi(db _x=,db _y=):x(_x),y(_y){};
      il poi operator -(const poi&A)const{return poi(x-A.x,y-A.y);}
      il bool operator <(const poi&A)const{return x==A.x?y<A.y:x<A.x;}
      }p1[N],p2[N],q[N];
      il db crs(poi A,poi B){return A.x*B.y-A.y*B.x;}
      il db dot(poi A,poi B){return A.x*B.x+A.y*B.y;}
      il bool spj(){
      int fg=;
      for(int i=;i<=n;++i)if(dcmp(p1[].x-p1[i].x)||dcmp(p1[].y-p1[i].y)){fg=;break;}
      for(int i=;i<=m;++i)if(dcmp(p1[].x-p2[i].x)||dcmp(p1[].y-p2[i].y)){fg=;break;}
      if(!fg){puts("");return true;}
      else return false;
      }
      il void convex(){
      sort(p2+,p2+m+);
      q[top=]=p2[];
      if(m==)return;
      for(int i=;i<=m;++i){
      while(top>&&dcmp(crs(q[top]-q[top-],p2[i]-q[top]))<=)top--;
      q[++top]=p2[i];
      }
      int now=top;
      for(int i=m-;i;--i){
      while(top>now&&dcmp(crs(q[top]-q[top-],p2[i]-q[top]))<=)top--;
      q[++top]=p2[i];
      }
      top--;
      }
      il bool judge(int a,int b){
      int i; poi p = p1[b]-p1[a];
      for(i=;i<=top;++i){
      int c = dcmp(crs(p, q[i]-p1[a]));
      if(c>)break;
      if(!c&&dcmp(dot(q[i]-p1[b], q[i]-p1[a]))>)break;
      }
      return i==top+?true:false;
      }
      int main(){
      #ifndef ONLINE_JUDGE
      freopen("bzoj1027.in","r",stdin);
      freopen("bzoj1027.out","w",stdout);
      #endif
      db tmp;
      scanf("%d%d",&n,&m);
      for(int i=;i<=n;++i)scanf("%lf%lf%lf",&p1[i].x,&p1[i].y,&tmp);
      for(int i=;i<=m;++i)scanf("%lf%lf%lf",&p2[i].x,&p2[i].y,&tmp);
      if(spj())return ;
      convex();
      memset(dis,0x3f,sizeof(dis));
      for(int i=;i<=n;++i)
      for(int j=;j<=n;++j)if(i!=j){
      if(judge(i,j))dis[i][j]=;
      }
      for(int k=;k<=n;++k)
      for(int i=;i<=n;++i)
      for(int j=;j<=n;++j){
      if(dis[i][j]>dis[i][k]+dis[k][j])
      dis[i][j] = dis[i][k]+dis[k][j];
      }
      int ans=inf;
      for(int i=;i<=n;++i)ans = min(ans, dis[i][i]);
      if(ans==inf)puts("-1"); else printf("%d\n",ans);
      return ;
      }

      bzoj1027

bzoj1027【JSOI2007】合金的更多相关文章

  1. bzoj1027 &lbrack;JSOI2007&rsqb;合金

    1027: [JSOI2007]合金 Time Limit: 4 Sec  Memory Limit: 162 MBSubmit: 2671  Solved: 703[Submit][Status][ ...

  2. bzoj千题计划123:bzoj1027&colon; &lbrack;JSOI2007&rsqb;合金

    http://www.lydsy.com/JudgeOnline/problem.php?id=1027 因为x+y+z=1,所以z=1-x-y 第三维可以忽略 将x,y 看做 平面上的点 简化问题: ...

  3. BZOJ1027 &lbrack;JSOI2007&rsqb;合金 【计算几何 &plus; floyd】

    题目 某公司加工一种由铁.铝.锡组成的合金.他们的工作很简单.首先进口一些铁铝锡合金原材料,不同种类的 原材料中铁铝锡的比重不同.然后,将每种原材料取出一定量,经过融解.混合,得到新的合金.新的合金的 ...

  4. 【bzoj1027】合金

    [bzoj1027]合金 分析 数形结合+计算几何+Floyd最小环. http://blog.csdn.net/popoqqq/article/details/40539273 虽然这样占大家的很不 ...

  5. bzoj 1027 &lbrack;JSOI2007&rsqb;合金(计算几何&plus;floyd最小环)

    1027: [JSOI2007]合金 Time Limit: 4 Sec  Memory Limit: 162 MBSubmit: 2970  Solved: 787[Submit][Status][ ...

  6. BZOJ 1027 &lbrack;JSOI2007&rsqb;合金

    1027: [JSOI2007]合金 Time Limit: 4 Sec  Memory Limit: 162 MBSubmit: 2605  Solved: 692[Submit][Status][ ...

  7. &lbrack;bzoj 1027&rsqb;&lbrack;JSOI2007&rsqb;合金(解析几何&plus;最小环)

    题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1027 分析: 首先因为一个合金的和为1,所以考虑2个材料合金能否合成一个需求合金的时候 ...

  8. 1027&colon; &lbrack;JSOI2007&rsqb;合金 - BZOJ

    Description 某公司加工一种由铁.铝.锡组成的合金.他们的工作很简单.首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同.然后,将每种原材料取出一定量,经过融解.混合,得到新的 ...

  9. &lbrack;JSOI2007&rsqb;合金

    Description 某公司加工一种由铁.铝.锡组成的合金.他们的工作很简单.首先进口一些铁铝锡合金原材料,不同种类的 原材料中铁铝锡的比重不同.然后,将每种原材料取出一定量,经过融解.混合,得到新 ...

  10. P4049 &lbrack;JSOI2007&rsqb;合金

    传送门 我数学可能白学了-- 因为三个数加起来等于\(1\),那么只要用前两个数就能表示,那么就能把每一种金属看成一个二维向量.考虑只有两个向量的时候,设这两个向量为\(a,b\),那么一个向量\(c ...

随机推荐

  1. 从零自学Hadoop&lpar;08&rpar;:第一个MapReduce

    阅读目录 序 数据准备 wordcount Yarn 新建MapReduce 示例下载 系列索引 本文版权归mephisto和博客园共有,欢迎转载,但须保留此段声明,并给出原文链接,谢谢合作. 文章是 ...

  2. 17、SQL基础整理(事务)

    事务 事务==流程控制 确保流程只能成功或者失败,若出现错误会自动回到原点 例: begin tran insert into student values('111','王五','男','1999- ...

  3. leetcode Same Tree python

    # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = ...

  4. BSGS算法&lpar;大步小步算法&rpar;

    计算\(y^x ≡ z \ mod\ p\) 中 \(x\) 的解. 这个模板是最小化了\(x\) , 无解输出\(No \ Solution!\) map<ll,ll>data; ll ...

  5. ArrayList 实现随机点名

    package lijun.cn.demo1; import java.util.ArrayList; import java.util.Random; public class CallName { ...

  6. HTTP各种特性

    一.Http客户端 1.浏览器.打开百度首页 2.Curl工具 二.CORS 跨域(浏览器的功能) 1.修改Server.js const http = require('http'); const ...

  7. git使用,多分支合并代码解决冲突,git删除远程分支,删除远程master默认分支方法

    git使用,多分支合并代码解决冲突,git删除远程分支,删除远程master默认分支方法提交代码流程:1.先提交代码到自己分支上2.切换到devlop拉取代码合并到当前分支3.合并后有变动的推送到自己 ...

  8. arcengine 正确绑定办法

    if (!RuntimeManager.Bind(ProductCode.Engine)) { if (!RuntimeManager.Bind(ProductCode.Desktop)) { Mes ...

  9. FileSystemWatcher监听文件是否有被修改

    作用:监听文件系统更改通知,并在目录或目录中的文件更改时引发事件. 需求:监听特定文件是否修改,然后做出相应的操作. 方法: ①利用一个线程,一直去查找该指定的文件是否有被修改,如果修改则操作特定步骤 ...

  10. C&num; WPF DataGrid 隔行变色及内容居中对齐

    C# WPF DataGrid 隔行变色及内容居中对齐. dqzww NET学习0     先看效果: 前台XAML代码: <!--引入样式文件--> <Window.Resourc ...