首页 > 代码库 > UVa 121 - Pipe Fitters
UVa 121 - Pipe Fitters
题目:在一个矩形中摆放圆,要求每行或每列的圆是相切的,问最多能放多少个。
分析:计算几何,数论。首先计算矩形摆放,然后计算交叉摆放(每行相同和相邻行差1个)求最大即可。
说明:╮(╯▽╰)╭当成最大摆放WA好几次。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; //题目方式摆放 int getmin(double x, double y) { int a = (int)x,m = 0; int b = (int)(2.0*(y-1.0)/sqrt(3.0))+1; if (m < a*b-b/2) m = a*b-b/2; a = (int)x; if (a+0.5 <= x && m < a*b) m = a*b; return m; } //最大数目摆放 int getmax(double x, double y) { int a = (int)x,m = 0; //n+1,n,n+1方式 while (a > 1 && y >= 1) { double d = (x-1.0)/(a-1.0); if (d >= 2) break; double r = sqrt(1.0-0.25*d*d); if (r < 0.5) r = 0.5; int b = (int)((y-1.0)/r)+1; if (m < a*b-b/2) m = a*b-b/2; a --; } //n,n,n方式 a = (int)x; while (a > 0 && y >= 1) { double d = 2*(x-1.0)/(2*a-1.0); if (d >= 2) break; if (d >= 1) { double r = sqrt(1.0-0.25*d*d); if (r < 0.5) r = 0.5; int b = (int)((y-1.0)/r)+1; if (m < a*b) m = a*b; } a --; } return m; } int main() { double x,y; while (cin >> x >> y) { int n = (int)x*(int)y,m = 0,p,q; p = getmin(x, y); if (p > m) m = p; q = getmin(y, x); if (q > m) m = q; if (m > n && x >= 1 && y >= 1) cout << m << " skew" << endl; else cout << n << " grid" << endl; } return 0; }
UVa 121 - Pipe Fitters
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。