Posts Tagged “tile”


Andrew Stankevich’s Contest #4
ZOJ2559 The Smart Bomb 53.76% (321/597)
ZOJ2560 I Just Called … 21.05% (76/361)
ZOJ2561 Order-Preserving Codes 18.28% (126/689)
ZOJ2562 More Divisors 30.14% (322/1068)
ZOJ2563 Long Dominoes 37.94% (148/390)
ZOJ2564 The Magic Wheel 17.11% (83/485)
ZOJ2565 Cracking SSH 50.25% (98/195)
ZOJ2566 Periodic Tilings 33.81% (47/139)
ZOJ2567 Trade 16.66% (97/582)
ZOJ2568 Counting Triangulations 16.31% (101/619)
ZOJ2569 Unfair Contest 28.57% (64/224)

这套题居然有11道,还是有不少好题的,尤其是ZOJ2566 Periodic Tilings,非常好的一道题,利用数学结论,可以转换为美丽的图论。还有ZOJ 2568是非常不错的计算几何模型动态规划;ZOJ 2561也是动态规划,用到了四边形不等式优化;ZOJ 2567,上下界最小流。

ZOJ2559 The Smart Bomb

downloadsource code (ZOJ2559.cpp) [math]

给定三个圆的圆心,要求圆不能相交,但可以相切,要使三个圆的半径和最大,问三个圆的半径各应该是多少。

显然要使三个圆两两相切,设三角形三边为a, b, c,三个圆半径为x, y, z就有
\left\{\begin{array}{l}x+y=c\\y+z=a\\z+x=b\end{array}\right.
有唯一解。

Comments 6 Comments »