Skip to content

11399: 【原1399】圆圈游戏

题目

题目描述

author: BreakVoid 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1399

Description

在无聊的时候,小X和Sharon会在纸上玩这样一个游戏。

我们可以将纸看做一个平面直角坐标系。Sharon会先在上面画出n个圆,并把每个圆的圆心以及半径都告诉小X。Sharon一向追求完美和简约,因此她画的n个圆中,任意两个圆不会出现相交或相切的情况。小X需要做的就是从这n个圆中选出若干个圆,使得选出的任意一个圆都不被另一个选出的圆包含。游戏的目标就是要选出尽量多的圆。

游戏一次一次进行着,小X已经对游戏的规则感到了厌倦,所以他决定修改游戏的规则。对于第i个圆,我们定义它的价值为\(w_i\)。新的游戏目标是使得选出的圆价值和最大(不一定数量最多)。但是圆圈可能很多,或者圆圈的分布非常奇怪,或者小X还有别的事情要做。所以他只好拜托你来帮他求出这个最大值了。

Input Format

第一行一个整数\(n\)表示圆圈的个数。

接下来\(n\)行每行4个整数\(x_i,~y_i,~r_i,~w_i\),分别表示第\(i\)个圆圆心的横坐标,纵坐标,第\(i\)个圆的半径,第\(i\)个圆的价值。

Output Format

共一行包含一个整数,表示选出圆的最大价值和。

Sample Input

3

3 4 2 3

6 4 7 5

9 4 1 4

Sample Output

7

数据规模与约定

共25个测试点,每个测试点4分,其中:

共7个测试点保证 n ≤ 16

共15个测试点保证 n ≤ 10000

对于所有的测试点保证 n ≤ 100000,半径和坐标的范围在[1, 10^8]内,每个圆的价值不会超过1000。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!