25875번 - World Cup Fever 다국어

문제

The 2018 World Cup was held recently in Russia. Some great soccer countries (e.g., Italy, Netherlands, Chile, USA) did not qualify for this World Cup. These countries have found out that they needed more effective passing.

Given the player positions for two teams, determine the minimum number of passes needed to get the ball from one player to another player. For the purposes of this problem, players do not change position, i.e., they do not move.

Player P₁ can pass the ball directly to P₂ if they are on the same team and no other player is in between the two players.

Let’s assume:

• P₁ and P₂ are on the same team
• P₁, P₂, P₃ form a line with P₃ between P₁ and P₂
• There are no other players on the line formed by P₁, P₂, P₃

Then,

• If P₃ is on the other team, P₁ cannot pass the ball directly to P₂.
• If P₃ is on the same team, P₁ can pass the ball to P₃ to pass it to P₂.

입력

The first input line contains an integer, n (2 ≤ n ≤ 11), indicating the number of players on each team. The second input line contains 2n integers, providing the (x,y) coordinates for the n players on Team 1; the first integer on this input line is the x coordinate for Player 1, the second integer is the y coordinate for Player 1, the third integer is the x coordinate for Player 2, etc. The third input line provides (in a similar fashion) the (x,y) coordinates for the n players on Team 2. Assume that all coordinates are integers between 1 and 999 (inclusive) and that all players are on distinct locations, i.e., no two players occupy the same spot (point).

Assume Player 1 on Team 1 has the ball and wants to pass the ball to Player n on Team 1. Assume that any player can pass the ball any distance.

출력

The output consists of a single integer, indicating the minimum number of passes needed to get the ball from Player 1 on Team 1 to Player n on Team 1. If it is not possible to get the ball from Player 1 to Player n, print -1.

제한

힌트