首页 > 代码库 > Bzoj1027 [JSOI2007]合金
Bzoj1027 [JSOI2007]合金
Submit: 3823 Solved: 1115
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
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
HINT
Source
由于a+b+c=1，第三维可以用前两维表示，所以可以不考虑。
二维情况下，几个点围成的区域就是它们可以表示出的区域。
枚举n中任意两点，若所有m点都在这两点所连有向线段的左边，则可以选。在邻接矩阵上标记出各点到另外点的转移关系，floyd求最小环即可。
然后特判所有点共点的情况。
——————
脑洞出一种奇怪的方法：
枚举凸包上某个点作为起点，遍历后面的凸包上点，如果m个点都在p[i] to p[i-2] 这条线段的左边，那么p[i],p[i-1],p[i-2]围成的三角形就没用了，可以把p[i-1]舍弃掉
枚举起点O(n)，遍历凸包O(n)，判是否可行O(m)，总时间复杂度O(n*n*m)
拍了半天没问题的样子，但是交上去过不了，目测是在判断能否围成环的时候出了bug，要么就是少了什么特判
还是先放着吧
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const double eps=1e-8; 10 const int mxn=100010; 11 struct Point{ 12 double x,y; 13 Point operator + (Point b){ return (Point){x+b.x,y+b.y};} 14 Point operator - (Point b){ return (Point){x-b.x,y-b.y};} 15 double operator * (Point b){return x*b.x+y*b.y;} 16 bool operator < (Point b)const{ 17 return x<b.x || (x==b.x && y<b.y); 18 } 19 }p[mxn],a[mxn],bas[mxn]; 20 typedef Point Vector; 21 double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;} 22 int n,m; 23 int ans; 24 bool judge(Point x,Point y){ 25 for(int i=1;i<=m;i++){ 26 double cro=Cross(y-x,a[i]-x); 27 if(cro<-eps)return 0; 28 if(fabs(cro)<eps && (x-a[i])*(y-a[i])>eps){ 29 return 0; 30 } 31 } 32 return 1; 33 } 34 35 int st[mxn],top,t2; 36 void Andrew(){ 37 sort(p+1,p+n+1); 38 for(int i=1;i<=n;i++){ 39 while(top>1 && Cross(p[st[top]]-p[st[top-1]],p[i]-p[st[top]])<0)top--; 40 st[++top]=i; 41 } 42 t2=top; 43 for(int i=n-1;i;i--){ 44 while(t2>top && Cross(p[st[t2]]-p[st[t2-1]],p[i]-p[st[t2]])<0)t2--; 45 st[++t2]=i; 46 } 47 for(int i=1;i<=t2;i++){ 48 printf("%.3f %.3f\n",p[st[i]].x,p[st[i]].y); 49 } 50 printf("fin\n");*/ 51 memcpy(bas,p,sizeof p); 52 for(int i=1;i<=t2;i++)p[i]=bas[st[i]]; 53 n=t2-1; 54 return; 55 } 56 void solve(int ST){ 57 // printf("st:%d\n",ST); 58 st[top=1]=ST; 59 for(int i=1,tmp=ST+1;i<n;i++,tmp++){ 60 if(tmp>n)tmp-=n; 61 if(top>1 && fabs(Cross(p[tmp]-p[st[top]],p[(tmp%n)+1]-p[tmp]))<eps)continue; 62 // printf("tmp:%d pt:%.3f %.3f\n",tmp,p[tmp].x,p[tmp].y); 63 bool flag=judge(p[st[top-1]],p[tmp]); 64 // printf("last:%.3f %.3f now:%.3f %.3f\n",p[st[top-1]].x,p[st[top-1]].y,p[tmp].x,p[tmp].y); 65 // printf("flag:%d\n",flag); 66 if(top>1 && flag){ 67 st[top]=tmp; 68 } 69 else if(judge(p[st[top]],p[tmp]))st[++top]=tmp; 70 else return; 71 } 72 if(top==2 && judge(p[st[top-1]],p[st[top]])){ 73 ans=min(ans,2);return; 74 } 75 if(st[top]==ST)top--; 76 if(!judge(p[st[top]],p[ST]))return; 77 ans=min(ans,top); 78 return; 79 } 80 bool SPJ(){ 81 for(int i=1;i<=n;i++) 82 if(fabs(p[i].x-p[1].x)>eps || fabs(p[i].y-p[1].y)>eps)return 0; 83 for(int i=1;i<=m;i++) 84 if(fabs(a[i].x-p[1].x)>eps || fabs(a[i].y-p[1].y)>eps)return 0; 85 return 1; 86 } 87 int main(){ 88 // freopen("Input.in","r",stdin); 89 int i,j; 90 scanf("%d%d",&n,&m); 91 for(i=1;i<=n;i++){ 92 scanf("%lf%lf%*lf",&p[i].x,&p[i].y); 93 } 94 for(i=1;i<=m;i++){ 95 scanf("%lf%lf%*lf",&a[i].x,&a[i].y); 96 } 97 if(!m){ 98 printf("0\n");return 0; 99 }100 if(SPJ()){101 printf("1\n");return 0;102 }103 Andrew();104 ans=0x3f3f3f3f;105 for(i=1;i<=n;i++){106 solve(i);107 }108 if(ans==0x3f3f3f3f || !ans)ans=-1;109 printf("%d\n",ans);110 return 0;111 }
——————
正解floyd：
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const double eps=1e-8;10 const int INF=0x3f3f3f3f;11 const int mxn=10010;12 struct Point{13 double x,y;14 Point operator + (Point b){ return (Point){x+b.x,y+b.y};}15 Point operator - (Point b){ return (Point){x-b.x,y-b.y};}16 double operator * (Point b){return x*b.x+y*b.y;}17 bool operator < (Point b)const{18 return x<b.x || (x==b.x && y<b.y);19 }20 }p[mxn],a[mxn],bas[mxn];21 typedef Point Vector;22 double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}23 int n,m;24 int ans;25 bool judge(Point x,Point y){26 for(int i=1;i<=m;i++){27 double cro=Cross(x-a[i],y-a[i]);28 if(cro>eps)return 0;29 if(fabs(cro)<eps && (x-a[i])*(y-a[i])>eps)return 0;30 }31 return 1;32 }33 bool SPJ(){34 for(int i=1;i<=n;i++)35 if(fabs(p[i].x-p[1].x)>eps || fabs(p[i].y-p[1].y)>eps)return 0;36 for(int i=1;i<=m;i++)37 if(fabs(a[i].x-p[1].x)>eps || fabs(a[i].y-p[1].y)>eps)return 0;38 return 1;39 }40 int mp[510][510];41 int main(){42 // freopen("Input.in","r",stdin);43 int i,j;44 scanf("%d%d",&n,&m);45 for(i=1;i<=n;i++){46 scanf("%lf%lf%*lf",&p[i].x,&p[i].y);47 // p[i].x*=10;p[i].y*=10;48 }49 if(!m){ printf("0\n");return 0;}50 for(i=1;i<=m;i++){51 scanf("%lf%lf%*lf",&a[i].x,&a[i].y);52 // a[i].x*=10;a[i].y*=10;53 }54 if(SPJ()){55 printf("1\n");56 return 0;57 }58 for(i=1;i<=n;i++){59 mp[i][i]=INF;60 for(j=1;j<=n;j++){61 if(i==j)continue;62 if(judge(p[i],p[j])) mp[i][j]=1;63 else mp[i][j]=INF;64 }65 }66 for(int k=1;k<=n;k++){67 for(i=1;i<=n;i++){68 for(j=1;j<=n;j++)69 mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);70 }71 }72 ans=INF;73 for(i=1;i<=n;i++)ans=min(ans,mp[i][i]);74 if(ans==INF)ans=-1;75 printf("%d\n",ans);76 return 0;77 }
Bzoj1027 [JSOI2007]合金
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。