問題一覧 > 通常問題

No.743 Segments on a Polygon

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 81
作問者 : 37zigen37zigen / テスター : はむこはむこ
8 ProblemId : 2063 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-10-06 00:17:32

問題文

$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。