No.743 Segments on a Polygon
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen
はむこ