C# – CodeForces – Tell Your World

Y = mX+B

This formula is the basics of the Cartesian coordinate system.
y-mxpb-graph

And about 70% of the knowledge, needed to solve problem B in the 2. Division of CodeForces. The problem looks like this:

There are n points on a coordinate plane, the i-th of which being (i, yi).

Determine whether it’s possible to draw two parallel and non-overlapping lines, such that every point in the set lies on exactly one of them, and each of them passes through at least one point in the set.

Input

The first line of input contains a positive integer n (3 ≤ n ≤ 1 000) — the number of points.

The second line contains n space-separated integers y1, y2, …, yn ( - 109 ≤ yi ≤ 109) — the vertical coordinates of each point.

Output

Output “Yes” (without quotes) if it’s possible to fulfill the requirements, and “No” otherwise.

Originally, once you read the problem, if you are unexperienced with similar problems (Star Sky and Banana Trees), you would simply open YouTube and put a nice song, then forget about programming. However, if you are willing to get deeper into problems like this, then you will start thinking something like this:

  • We have minimum 3 points given;
  • These 3 points either lay on the same line or there are 3 different lines connecting them;
  • Both cases are ok. In general.
  • Thus, we take the first 3 points in the following order (p1 and p2), (p1 and p3), (p2 and p3). For each of these two points, we calculate the line on which they lay. Then we start putting all the other points in the set. For the points, that do not belong to the line of the two points, we calculate whether there is a single line, that can go though them.
  • If yes, then we check whether the two lines are parallel. If we find only one case of the 3, where we have parallel lines, then we simply can state that we have found a possible solution.

With C#, this implementation looks like this:

To state that the lines are parallel, their slopes should be equal. Thus we check it with this:

Enjoy! 🙂

About

A VBA Developer.

Tagged with: , ,