• 21

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

You are given a set of line segments, and your goal is to 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 endpoints (x1, y1) and (x2, y2)
Output
Line 1: 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 one of their endpoints. They never cross, overlap, intersect, or touch midway.
No segment reduces to a point: for every segment, the two endpoints are distinct.
Example
Input
```3
0 0 10 10
10 10 10 0
0 0 10 0```
Output
`4`

A higher resolution is required to access the IDE   Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
Online Participants