JOIN
Get Time

   Problem Statement  

 Problem Statement for BearBall

Problem Statement

    

N bears are playing a game. For the purpose of this problem, each bear is just a single point in the plane. You are given the coordinates of the bears: the int[]s x and y, each with N elements. For each valid i there is a bear at (x[i], y[i]).



The game they play is played in rounds. There is a single ball. At the beginning of each round one of the bears holds the ball. This bear chooses a direction and throws the ball in that direction. The ball will travel along a straight line. As soon as the ball hits another bear for the first time, that bear will catch the ball and the round will end. It is not allowed to throw the ball in a direction where it won't hit any other bear.



At the beginning of the game, the bears choose two special roles: one bear will be the Startbear and another bear will be the Goalbear. The Startbear has the ball at the beginning of the game. The game ends when the Goalbear gets the ball. Bears always play optimally ? they always finish the game in the smallest possible number of rounds.



There are exactly N*(N-1) ways to choose the Startbear and the Goalbear. For each of those ways, determine the smallest possible number of rounds the game may take. Return the sum of those N*(N-1) numbers.

 

Definition

    
Class:BearBall
Method:countThrows
Parameters:int[], int[]
Returns:int
Method signature:int countThrows(int[] x, int[] y)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 1500, inclusive.
-x will contain exactly N elements.
-y will contain exactly N elements.
-Each element in x and in y will be between -20,000 and 20,000, inclusive.
-No two points will coincide.
 

Examples

0)
    
{1,4,2}
{1,10,7}
Returns: 6

There are three bears. They stand at (1,1), (4,10), and (2,7).



There are six ways to choose the Startbear and the Goalbear. In each of those six cases the game will have a single round, because the Startbear can throw the ball directly at the Goalbear. So, the answer is 6.

1)
    
{0,0,0,1,1}
{0,1,2,0,1}
Returns: 22

There are five bears. They stand at (0,0), (0,1), (0,2), (1,0), and (1,1).



There are 20 ways to choose the two special bears. In 18 of those 20 ways a single throw is enough. In each of the remaining two ways the bears need two rounds of the game.



Consider the situation when the Startbear is at (0,0) and the Goalbear is at (0,2). This game cannot be won in a single round: if the Startbear throws a ball in the direction of the Goalbear, the ball will hit the bear at (0,1) and that bear will catch it.



There are multiple ways to win that game in two rounds. For example, after the Startbear hits the bear at (0,1), that bear will throw the ball to the Goalbear. Another optimal strategy is to start by throwing the ball from (0,0) to (1,1). This is shown in the figure below; the bear with the ball is painted red.



2)
    
{5,7,9,11}
{4,3,2,1}
Returns: 20
3)
    
{10,10,50,50,90,90}
{5,17,5,17,5,17}
Returns: 34
4)
    
{-100, -90, -80, -70, -85, -90, 0, 20}
{-5, -8, -13, -21, -13, -13, -13, -69}
Returns: 68

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2016 TCO Algorithm Round 2C - Division I, Level One
       2016 TCO Algorithm Parallel Round 2C - Division I, Level One