首先注意到所有的数都在整数格点上，而且半径只有两种，而且都很小。 我们可以发现，
一个0.58半径的圆只会影响到周围4格，一个1.31半径的圆只会影响到周围12格（见图）

半径1.31的影响范围            半径0.58的影响范围
      .XX.                       ....
      XXXX                       .XX.
      XXXX                       .XX.
      .XX.                       ....

于是发现，一个格子的状态（被覆盖的面积），仅仅取决于它周围的12个格子！ 而这个状
态的数目，只有3^4*2^8=20736种！

于是写一个simpson暴力，把20736个状态预处理出来。但这一步要花大约2秒，会tle，
因此必须打表。
但直接打表会超代码长度限制。 我们观察这个表，发现连续的重复的段很多，于是用一个
简单的压缩，把一段相同的数（精确到5位小数就绰绰有余了）用二元组[a,b]表示出来
，a出现了b次。
然后进一步压缩，因为只出现了0～9，其他的字符都被浪费了，于是转成64进制（0～9,
A~Z,a~z和两个其他字符），这样一个二元组用5个字符就能表示了。
这时候表只有不到20K了，就可以装下了。

然后任务就简单了，一个圆只会影响到周围的格子，用hash表记录某个格子被影响的状态，
然后统计一下即可，整个过程是线性的。

• orz (738) JiaJunpeng 2011-12-25 19:43:10
  • Re:orz (5) peargobble 2011-12-25 20:05:51
    • Re:orz (9) dut200901102 2011-12-25 21:24:18