No.743 Segments on a Polygon

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 45
作問者 : 37zigen37zigen / テスター : はむこはむこ
4 ProblemId : 2063 / 出題時の順位表

問題文

$M$頂点の凸多角形があります。
凸多角形の頂点には時計回りに番号$0,1,2,...,M-1$が割り振られています。
ここで、線分を$N$回追加します。
$i$回目に追加した線分は番号$a_i$の頂点と番号$b_i$の頂点を結びます。
追加した線分同士がなす交点の数を数えてください。

ただし追加される線分は以前に追加された線分と端点を共有しないとします。
つまり$i≠j$のとき$a_i≠a_j $かつ$b_i≠b_j$かつ$a_i≠b_j$です。
また、$1$つの交点が$k$本の線分からなるとき$1$つの交点として数えず、$k(k-1)/2$個の交点として数えてください。

このとき、任意の$M$頂点の凸多角形について交点の数は一致することに注意してください。 より正確には$M,N,a_i,b_i$が与えられれば交点の数は定まることに注意してください。

入力

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$a_3$ $b_3$
$\vdots$
$a_N$ $b_N$

$1≦N≦10^5$
$3≦M≦2×10^5$
$a_i,b_i$は整数
$0≦a_i,b_i≦M-1$
$a_i≠a_j (i≠j)$
$b_i≠b_j (i≠j)$
$a_i≠b_j$ ($i=j$の時も成立)

出力

線分がなす交点の数を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 6
2 3
1 0
4 5
出力
0

サンプル2
入力
9 18
11 6
14 2
0 17
7 13
4 12
1 16
10 3
8 15
5 9
出力
13

サンプル3
入力
6 12
9 11
3 10
4 6
1 5
0 7
2 8
出力
7

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。