問題一覧 > 通常問題

No.743 Segments on a Polygon

レベル : / AI推定難易度 : 1225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 85
作問者 : 37zigen / テスター : はむこ
お気に入りにしたユーザー ProblemId : 2063 / 自分の提出
問題文最終更新日: 2018-10-06 00:17:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 201 (順位表) の他の問題:

Problem Statement

There is a convex polygon with $M$ vertices.
The vertices of the convex polygon are numbered $0,1,2,...,M-1$ in clockwise order.
Now, line segments are added $N$ times.
The segment added at the $i$-th time connects the vertex numbered $a_i$ and the vertex numbered $b_i$.
Count the number of intersection points formed by the added segments.

It is guaranteed that an added segment does not share an endpoint with any previously added segment.
That is, when $i≠j$, we have $a_i≠a_j $, $b_i≠b_j$, and $a_i≠b_j$.
Also, when $1$ intersection point is formed by $k$ segments, do not count it as $1$ intersection point; count it as $k(k-1)/2$ intersection points.

Note that the number of intersection points is the same for any convex polygon with $M$ vertices. More precisely, note that the number of intersection points is determined once $M,N,a_i,b_i$ are given.

Input

$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$ are integers
$0≦a_i,b_i≦M-1$
$a_i≠a_j (i≠j)$
$b_i≠b_j (i≠j)$
$a_i≠b_j$ (this also holds when $i=j$)

Output

Output the number of intersection points formed by the segments.
Print a newline at the end.

Sample

Sample 1
Input
3 6
2 3
1 0
4 5
Output
0

Sample 2
Input
9 18
11 6
14 2
0 17
7 13
4 12
1 16
10 3
8 15
5 9
Output
13

Sample 3
Input
6 12
9 11
3 10
4 6
1 5
0 7
2 8
Output
7

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