814D - An overnight dance in discotheque@tree dp||greedy

69 阅读 0 评论 46 点赞

我是靠谱客的博主超级绿茶，最近开发中收集的这篇文章主要介绍814D - An overnight dance in discotheque@tree dp||greedy，觉得挺不错的，现在分享给大家，希望可以做个参考。

题意

给出 n 个圆，每个圆给出圆心坐标和半径。任意两个圆之间最多只有一个公共点。将这 n 个圆放到两个坐标系内，使被奇数个圆覆盖的区域的面积最大，求这个最大面积。

任意两个圆最多只有一个公共点，也就是说两个圆的关系要么外离，要么内含。一个圆最多被一个圆直接包含。由此联想到树的结构，准确的说是森林，进而可以想到Tree DP的做法。

后来看了官方神犇的题解，这个题完全可以贪心来做。
首先，对于每一摞套起来的圆，从大到小进行排序。最大圆全都有效时面积当然是最大的。因此，把最大的那个圆放在一个坐标系内，其他圆放到第二个坐标系内。第二个坐标系内的有效区域面积，就是奇数大的圆的面积之和减去偶数大的圆的面积之和。

http://codeforces.com/blog/entry/52449

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。