JOIN
Get Time

   Problem Statement  

 Problem Statement for NoRightTurn

Problem Statement

    

This problem has a non-standard time limit: 5 seconds.

Roger the Robot has been sent to explore a planet. The surface of the planet can be thought of as a two-dimensional plane. You are given two int[]s x and y. The planet has N interesting points described by these int[]s. The i-th interesting point has coordinates (x[i], y[i]). No three interesting points will be collinear.

Roger will choose a permutation of {0,1,...,N-1}, and will visit the points in that order. Roger will travel in a straight line in between points. There are two conditions he must follow:

  1. He must never cross his own path (that is, if we look at the line segments formed by the path, no two segments strictly intersect).
  2. Due to rather unfortunate oversight, Roger is incapable of making any right turns. This means that for any three consecutive points that he visits, these three points constitute a counter-clockwise orientation.

Your job is to count the number of valid paths Roger can take. Let f(i) denote the number of valid paths Roger can take provided he starts at point i. Return a int[] containing N elements. The i-th element in this array must be f(i) modulo 1,000,000,007.

 

Definition

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

Constraints

-x will have between 3 and 100 elements, inclusive.
-y will have exactly the same number of elements as x.
-Each element of x,y will be between -1,000 and 1,000, inclusive.
-All pairs (x[i], y[i]) will be distinct.
-No three points will be collinear.
 

Examples

0)
    
{-10, 0, 10}
{10, -10, 10}
Returns: {1, 1, 1 }
These three points form a triangle. There are three valid paths as follows: 0->1->2, 1->2->0, and 2->0->1. Thus, each point has one valid path starting from it.
1)
    
{0,0,-3,-3,3,3}
{-1,1,-3,3,-3,3}
Returns: {5, 5, 1, 1, 1, 1 }

Here are the 14 valid paths, and the breakdown by startpoint:

2)
    
{14,13,12,11,10,9,8,7,6,5,4,3,2,1}
{1,4,9,16,25,36,49,64,81,100,121,144,169,196}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
3)
    
{0, 2,-2, 4,-4, 2,-2, 0}
{1, 2, 2, 4, 4, 6, 6, 5}
Returns: {1, 1, 1, 1, 1, 1, 1, 7 }
4)
    
{0,0,-10,-20,10,20}
{-10,-20,10,20,10,20}
Returns: {5, 1, 5, 1, 5, 1 }
5)
    
{222,269,91,114,-355,-241,-61,134,-146,-245,-158,289,230,-247,140,-301,
-125,-9,334,-21,-277,-336,-925,-81,388,-130,-96,327,-71,-327,-383,-214,
-299,199,-221,-240,202,-331,823,385,-165,247,50,-935,177,83,-290,-373,
173,-264,-231,-304,119,-307,-297,-243,396,-339,98,87,56,-43,142,-375,
-190,105,-135,188,34,227,24,56,249,390,-258,61,-216,-16,-79,-37,-345,
-135,332,-189,-334,-386}
{-125,67,99,-349,-273,8,-145,182,110,-260,-71,79,-312,-224,-50,288,82,
-6,248,44,39,121,-965,-202,9,-289,-236,340,-265,245,-294,253,-65,-338,
-381,210,-183,205,0,-70,349,-308,-142,915,15,-121,3,346,-136,146,-238,
-304,-44,64,-202,-213,-98,15,-197,225,-355,268,-30,-178,313,-375,96,264,
-384,166,294,21,-317,250,24,374,26,-299,303,92,-43,-33,132,-57,165,-297}
Returns: 
{77, 153, 93, 19, 48, 370, 39, 63, 63, 41, 261, 69, 20, 75, 71, 21, 127, 158, 29, 237, 196, 89, 1, 300, 17, 23, 111, 1, 64, 20, 23, 73, 29, 7, 16, 45, 81, 21, 1, 46, 30, 9, 57, 1, 166, 61, 61, 8, 41, 172, 153, 30, 225, 56, 34, 177, 5, 28, 63, 69, 57, 271, 302, 14, 32, 10, 146, 39, 6, 43, 30, 275, 1, 9, 315, 13, 134, 56, 71, 103, 36, 50, 13, 195, 17, 8 }

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:
       Single Round Match 652 Round 1 - Division I, Level Three