首页 > 代码库 > bzoj1027: [JSOI2007]合金
bzoj1027: [JSOI2007]合金
http://www.lydsy.com/JudgeOnline/problem.php?id=1027
完全不会写然后听隔壁未来IOI爷讲的 Orzccz
因为第三维可以由前两维推出所以就变成了一些点
然后题目就可以转化为求一个最小的凸多边形使得所有点都在这个凸多边形内
然后就可以floyd
对于原材料合金中的两个,为坐标系中的两点,若所有需要的合金都在其一侧(不妨统一设为左侧),则连一条长度为1的有向边。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define rep(i,l,r) for(int i=l;i<=r;++i) 7 using namespace std; 8 const int N=520; 9 typedef double d; 10 int n,m,ans,f[N][N],flag; 11 d c; 12 struct point{ 13 d x,y; 14 }a[N],b[N]; 15 typedef point vector; 16 const d eps=1e-7; 17 vector operator - (point a,point b){ 18 return (vector){a.x-b.x,a.y-b.y}; 19 } 20 d cross(vector a,vector b){ 21 return a.x*b.y-a.y*b.x; 22 } 23 d cross(point a,point b,point c){ 24 return cross(b-a,c-a); 25 } 26 d dot(vector a,vector b){ 27 return a.x*b.x+a.y*b.y; 28 } 29 d dot(point a,point b,point c){ 30 return dot(b-a,c-a); 31 } 32 int main(){ 33 scanf("%d%d",&n,&m); 34 rep(i,1,n)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&c); 35 rep(i,1,m)scanf("%lf%lf%lf",&b[i].x,&b[i].y,&c); 36 memset(f,60,sizeof f); 37 rep(i,1,n) rep(j,1,n) { 38 flag=1; 39 rep(k,1,m){ 40 c=cross(b[k],a[i],a[j]); 41 if(c>eps||(fabs(c)<eps&&dot(b[k],a[i],a[j])>eps)){ 42 flag=0; 43 break; 44 } 45 } 46 if(flag) f[i][j]=1; 47 } 48 rep(k,1,n) rep(i,1,n) rep(j,1,n) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); 49 ans=1e9; 50 rep(i,1,n) ans=min(ans,f[i][i]); 51 printf("%d\n",ans>=1e9?-1:ans); 52 }
bzoj1027: [JSOI2007]合金
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。