Back
Close
  • 9

What will I learn?

Graph theoryTopology

Statement

 Goal

You are given a set of line segments.
- Two segments may meet at one of their endpoints. They never cross, intersect, or touch midway.
- No segment reduces to a point: for every segment, the two endpoints are distinct.

Compute a cyclic continuous curve that:
* does not intersect any endpoint of a segment
* intersects every segment at least once
* minimizes the number of intersections
Your algorithm should return said minimum number of intersections.

Two examples are given at https://imgur.com/a/8kUNhS6, a valid and optimal one and an invalid one crossing an endpoint.

The cyclic curve may self-intersect when necessary. This does not count as crossing a line segment.
Input
Line 1: An integer n, the number of segments in S
n next lines : four integers x1 y1 x2 y2 describing a segment of S with two extremities (x1, y1) and (x2, y2)
Output
Line 1: c the minimum number of segments that should be crossed in a cyclic curve that crosses every segment at least once.
Constraints
1 <= n <= 25
1 <= xi, yi<= 100
Two segments may meet at on of their extremities, they do not cross, they do not overlap.
No segment is empty : for every segment, the two extremities are distinct.
Example
Input
3
0 0 10 10
10 10 10 0
0 0 10 0
Output
4
Solve it

A higher resolution is required to access the IDE

codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants