[Problem proposal] Segment Intersection Test

[HeRaNO]

Problem name: Segment Intersection Test

Problem

Given $n$ segments on a 2D plane. Judge if:

• exist two segments intersect strictly (the intersection is not an endpoint of the two segments);
• exist two segments intersect (allow the intersection to be an endpoint of the two segments).

Constraint

• $1 \leq n \leq 10^5, 0\le x_i,y_i\le 10^9$

Solution / Reference

• https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
• https://github.com/cjj490168650/Template/blob/main/Geometry.cpp#L623

Input 1

2
1 1 1 0
1 1 1 2

Output 1

NO
YES

Segment $(1,1)-(1,0)$ and $(1,1)-(1,2)$ intersect, but the intersection is the endpoint of the two segments.

Input 2

2
1 1 1 0
10 10 10 20

Output 2

NO
NO

Input 3

2
1 1 1 3
1 2 2 2

Output 3

YES
YES

Segment $(1,1)-(1,3)$ and $(1,2)-(2,2)$ intersect, and the intersection is not an endpoint of any segment.

[maspypy]

Thank you for your proposal and sorry for leaving it unattended for so long. I think it's a good suggestion.

Regarding the format of the questions, I think it would be beneficial to output the indices of the line segments as well.

Also, this algorithm can output "min(M,K) intersections" if we define M as the number of intersections, so it's worth considering that format as well, don't you think?

As long as we can detect intersections, determining whether they are strict or not is straightforward, so I don't think it's necessary to distinguish between strict and non-strict intersections.

[HeRaNO]

Thanks for your thoughtful suggestion! It's a good idea to output the indices of the line segments.
Maybe we can ask for $p$ intersections ($p$ is specified by the input), and output $p$ pairs of segments
which are intersect, which I think will be better. Please feel free to modify the problem.

[maspypy]

[Problem Statement] $n$ segments $s0,\ldots,s{n-1}$ and a positive integer $k$ is given. Let $S$ denote the set of pairs $(i,j)$ such that $0 \leq i \lt j \lt n$ and $s_i$ and $s_j$ have at least one common point (including their endpoints). Output $m=\min(k,|S|)$ and $m$ pairs contained in $S$.

All segments $s_i$ are guaranteed to be non-degenerate, i.e., they have positive length.

[Output Format] $m$ $i_0$ $j0$ $\vdots$ $i{m-1}$ $j_{m-1}$

[maspypy]

Preparing for judging this problem can be a little challenging, so it might take quite a bit of time to get ready.