C# – CodeForces – Tell Your World

Posted on September 12, 2017 by

Vitosh Posted in C Sharp Tricks, CodeForces

Y = mX+B

This formula is the basics of the Cartesian coordinate system.

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, y_i).

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 y₁, y₂, …, y_n ( - 10⁹ ≤ y_i ≤ 10⁹) — 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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Startup
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        List<double> liInput = ReadLineAndParseToList();
        bool returnAnswer = false;
        returnAnswer |= HasAnswer(1, liInput[0], 2, liInput[1], liInput);
        returnAnswer |= HasAnswer(1, liInput[0], 3, liInput[2], liInput);
        returnAnswer |= HasAnswer(2, liInput[1], 3, liInput[2], liInput);
        Console.WriteLine("{0}",returnAnswer ? "Yes":"No");
    }

    public static bool HasAnswer (double ax, double ay, double bx, double by, List<double>liInput )
    {
        List<double> liInputSomething = new List<double>(liInput);
        List<double> liLeftX = new List<double>();
        List<double> liLeftY = new List<double>();

        double mA; //slope
        double bA; //intersect

        mA = ((ay - by) / (ax - bx));
        bA = ay - mA*ax;

        //find which are on the line
        for (int i = 0; i < liInputSomething.Count; i++)
        {
            if (liInputSomething[i]!= mA * (i+1) + bA)
            {
                liLeftY.Add(liInputSomething[i]);
                liLeftX.Add(i+1);
            }
        }

        if (liLeftY.Count == 0 || liLeftY.Count == liInputSomething.Count)
        {
            return false;
        }
        else if (liLeftY.Count == 1)
        {
            return true;
        }
        else //find whether the rest 2 or more are on a line
        {
            ay = liLeftY[0];
            ax = liLeftX[0];
            by = liLeftY[1];
            bx = liLeftX[1];
            
            double mB = (ay - by) / (ax - bx);
            double bB = ay - mB * ax;

            if (mB!= mA)
            {
                return false;
            }

            for (int i = 0; i < liLeftY.Count; i++)
            {
                if (liLeftY[i] != mB * liLeftX[i] + bB)
                {
                    return false;
                }
            }
            return true;
        }
    }

    public static List<double> ReadLineAndParseToList()
    {
        return Console.ReadLine().Split().Select(double.Parse).ToList();
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

class Startup

{

static void Main()

{

int n = int.Parse(Console.ReadLine());

List<double> liInput = ReadLineAndParseToList();

bool returnAnswer = false;

returnAnswer |= HasAnswer(1, liInput[0], 2, liInput[1], liInput);

returnAnswer |= HasAnswer(1, liInput[0], 3, liInput[2], liInput);

returnAnswer |= HasAnswer(2, liInput[1], 3, liInput[2], liInput);

Console.WriteLine("{0}",returnAnswer ? "Yes":"No");

}

public static bool HasAnswer (double ax, double ay, double bx, double by, List<double>liInput )

{

List<double> liInputSomething = new List<double>(liInput);

List<double> liLeftX = new List<double>();

List<double> liLeftY = new List<double>();

double mA; //slope

double bA; //intersect

mA = ((ay - by) / (ax - bx));

bA = ay - mA*ax;

//find which are on the line

for (int i = 0; i < liInputSomething.Count; i++)

{

if (liInputSomething[i]!= mA * (i+1) + bA)

{

liLeftY.Add(liInputSomething[i]);

liLeftX.Add(i+1);

}

if (liLeftY.Count == 0 || liLeftY.Count == liInputSomething.Count)

{

return false;

}

else if (liLeftY.Count == 1)

{

return true;

}

else //find whether the rest 2 or more are on a line

{

ay = liLeftY[0];

ax = liLeftX[0];

by = liLeftY[1];

bx = liLeftX[1];

double mB = (ay - by) / (ax - bx);

double bB = ay - mB * ax;

if (mB!= mA)

{

return false;

}

for (int i = 0; i < liLeftY.Count; i++)

{

if (liLeftY[i] != mB * liLeftX[i] + bB)

{

return false;

}

return true;

}

public static List<double> ReadLineAndParseToList()

{

return Console.ReadLine().Split().Select(double.Parse).ToList();

}

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

            if (mB!= mA)
            {
                return false;
            }

if (mB!= mA)

{

return false;

}

Enjoy! 🙂

Tagged with: C#, Cartesian, Coordiante system

C# – CodeForces – Tell Your World

Related posts: