每日一水第41弹(world final 09 D)

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77398#problem/D

题意:求一个最小的圆将四个圆放进去。

这题要想把每一种分类情况考虑清楚无疑是不明智的。

考虑搜索。

二分答案之后,现在有一个大圆,四个小圆。

第一个最大的小圆先放进来,这个圆肯定会和大圆相内切,然后接下来三个圆依次放进来,每个圆肯定会和之前已经放进来的两个圆相切,枚举跟哪两个相切,算出可能的圆心位置,最后判断一下是否满足所有圆都在里面了。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注