TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4249
  • 問題
  • P4249打气球
    制限 : 時間制限 : - MS   メモリ制限 : 265536 KB
    審判説明 : 1s
    問題説明

    周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏,何老板很感兴趣。
    店家立了一块布,布上画了N*N的方格,有的方格里挂上了气球,有的没有。
    游戏规则如下:
    第1步.观察。如果每一行都至少有一个方格没有气球,同时每一列都至少有一个方格没有气球,游戏结束。否则进行第2步。
    第2步.抛骰子。店家拿出一个特制的骰子,该骰子有N个面,上面依次有1到N这N个数字。玩家先后抛两次骰子,设第一次抛出的数字为x,设第二次抛出的为y (注:抛出的数字是随机的)。
    第3步.打气球。若坐标为(x,y)的格子里有气球,玩家必须将其打爆。子弹1块钱一发。如果该格子没有气球,忽略该格子,玩家不用开枪,但玩家也需要支付给店家1块钱。
    第4步.继续。执行第1步。

    何老板是个神枪手,他能做到百发百中。他想你帮他算算,对于当前给出的这局游戏,预计要花多少钱才能结束。

    入力形式

    第一行,两个整数n和m,n表示方格的尺寸,m表示游戏开始时,有m个格子里是没有气球的。
    接下来m行,每行两个整数x,y,表示坐标为x,y的格子里没有气球。

    出力形式

    一行,一个实数,完成游戏预计花费,保留2个小数位。

    サンプル入力 1

    5 2
    2 3
    4 1

    サンプル出力 1

    11.77

    サンプル入力 2

    2 2
    1 1
    1 2

    サンプル出力 2

    2.00

    サンプル入力 3

    1 1
    1 1

    サンプル出力 3

    0.00

    ヒント

    \(1 ≤ n ≤ 2*10^3\)
    \(0 ≤ m ≤ min(n^2, 2*10^4)\)
    \(1≤x,y≤n\)


    ソース  改编自CF 398B