Connection Status:
Competition Arena > NoRightTurn

NoRightTurn

SRM 652 · 2015-01-29 · by lg5293

SRM 652 · 2015-01-29 · by lg5293 · Geometry, Search
Class Name: NoRightTurn
Return Type: int[]
Method Name: countWays
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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 }

Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NoRightTurn with a public method vector<int> countWays(vector<int> x, vector<int> y) · 55 test cases · 2 s / 256 MB per case

Submitting as anonymous