「LOJ 2586」「APIO2018」选圆圈

LOJ #2586

题意

平面上有$n$个圆,编号$1..n$

重复如下操作直到不存在圆

  1. 选择一个半径最大的圆,如果有多个,选择编号最小的

  2. 把所有与第1步选出的圆有交的圆删除

其中两个圆有交当且仅当存在一个点,这个点同时被两个圆包含,包含定义为点在圆内或者圆上

$n\le 3*10^5$

Read more