Back
Close
  • 11

Statement

 Goal

Windmill Process --------------------------------------------------------------------------------------------------------------------------

Given a finite plane S having at least three points. The windmill process can be define as follow:

- Start with a line going through a point PS
- Rotate clockwise around the pivot P until the line hits another point Q of S.
- The point Q now takes over as the new pivot.

This process continues until there is N changes of pivot.

Objectives --------------------------------------------------------------------------------------------------------------------------

Given :
- all points of S (there will never be three collinear points in S)
- the starting pivot P
- the number N of pivot changes

Your objective is to make a simulation of this process. You should output :
- The index of the pivot
- For each point, the number of times it has been a pivot

Definition of S --------------------------------------------------------------------------------------------------------------------------

S is a plane of 800 x 600
Position (X, Y) = (0, 0) is at the bottom left of S
The line will always start horizontally
The line will never starts aligned with another point
All point coordinates are integers.

Example --------------------------------------------------------------------------------------------------------------------------

Let's assume we have K=3 points (x, y) at:
- #0: (200,200)
- #1: (400,300)
- #2: (400,100)
and N == 3

The starting point P is #1 so the line starts horizontally at 400, 300.
The line turns Clockwise by 90 degrees and hits the point 2. It becomes the new pivot (1st time).
The line continues to turn and hits the point 0 after around 120 degrees. It becomes the new pivot (1st time).
The line turns again around 120 degrees and hits point 1 which becomes the pivot (2nd time).

As a result after 3 changes of pivot the result is :

1
1
2
1

The first 1 is for the pivot index and the rest is the number of time each point was a pivot.

Extra Information --------------------------------------------------------------------------------------------------------------------------

This puzzle has been inspired from a problem proposed during the international mathematical olympiad in 2011 (https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_2) and there is a nice explanation of this problem in one video of 3Blue1Brown (https://www.youtube.com/watch?v=M64HUIJFTZM)
Input
Line 1: Number of points on S, called K
Line 2: Number of pivot changes, called N
Line 3: Index P of the starting pivot (0-indexed)
Next K lines: Two integers for the position of each point X, Y
Output
Line 1: The index of the current pivot
K lines: One integer for the number of times each point was a pivot
Constraints
2 < K ≤ 30
0 < N ≤ 10^12
0 ≤ X ≤ 800
0 ≤ Y ≤ 600

The line will never starts aligned with another point
Example
Input
3
3
1
200 200
400 300
400 100
Output
1
1
2
1
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