A higher resolution is required to access the IDE

- 43

## Learning Opportunities

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

## Statement

## Goal

**Windmill Process**--------------------------------------------------------------------------------------------------------------------------

Given a finite plane

**at least**three points. The windmill process can be define as follow:

- Start with a line

`ℓ`going through a point

`P`∈

- Rotate

`ℓ`

**clockwise**around the pivot

`P`until the line hits another point

`Q`of

- 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

- 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 --------------------------------------------------------------------------------------------------------------------------

Position (X, Y) = (0, 0) is at the bottom left of

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`=

- #0: (200,200)

- #1: (400,300)

- #2: (400,100)

and

`N`==

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

`K`

**Line 2:**Number of pivot changes, called

`N`

**Line 3:**Index

`P`of the starting pivot (

**0-indexed**)

**Next**Two integers for the position of each point

`K`lines:`X`,

`Y`

Output

**Line 1:**The index of the current pivot

**One integer for the number of times each point was a pivot**

`K`lines:Constraints

2 <

0 <

0 ≤

0 ≤

The line

`K`≤ 300 <

`N`≤ 10^120 ≤

`X`≤ 8000 ≤

`Y`≤ 600The line

`ℓ`will never starts aligned with another pointExample

Input

3 3 1 200 200 400 300 400 100

Output

1 1 2 1

A higher resolution is required to access the IDE