Program to see how many points lie strictly inside a convex polygon The program takes in a set of coordinates that defines the polygon. It then takes in a set of points. The idea is to find out how many of these points lie strictly inside the convex polygon (not on the edge or outside). First the program checks if the first set of points form a convex polygon or not. If yes, the program proceeds. Then each point is checked to see if it is strictly inside the convex polygon. If yes, count variable is increased. Here is the code:

#include &lt;iostream&gt;
#include &lt;vector&gt;

// Calculate perpendicular dot product
int perdot(const std::pair&lt;int, int&gt; a, const std::pair&lt;int, int&gt; b, const std::pair&lt;int, int&gt; c)
{
    int ab_x = b.first - a.first;
    int ab_y = b.second - a.second;
    int ac_x = c.first - a.first;
    int ac_y = c.second - a.second;
    int per_dot = ab_x * ac_y - ab_y * ac_x;
    if(per_dot &lt; 0)
    {
        return -1;
    }
    else if(per_dot &gt; 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

// Check if given set of points form a convex polygon
bool is_convex(const std::vector&lt;std::pair&lt;int, int&gt;&gt;&amp; convex_polygon)
{
    int n = convex_polygon.size();
    int sense = perdot(convex_polygon[n - 1], convex_polygon[0], convex_polygon[1]);
    for(int i = 0; i &lt; n - 1; i++)
    {
        int new_sense;
        if(i == (n - 2))
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[0]);
        }
        else
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[i + 2]);
        }
        if(sense == 0)
        {
            sense = new_sense;
        }
        if(new_sense == (-sense) &amp;&amp; sense != 0)
        {
            return false;
        }
    }
    return true;
}

// Check if a point is STRICTLY inside the convex polygon
bool is_inside(const std::vector&lt;std::pair&lt;int, int&gt;&gt;&amp; convex_polygon, const std::pair&lt;int, int&gt; point)
{
    int n = convex_polygon.size();
    int sense = perdot(convex_polygon[n - 1], point, convex_polygon[0]);
    if(sense == 0)
    {
        return false;
    }

    for(int i = 0; i &lt; n - 1; i++)
    {
        int new_sense;
        new_sense = perdot(convex_polygon[i], point, convex_polygon[i + 1]);
        if(new_sense == (-sense) || new_sense == 0)
        {
            return false;
        }
    }
    return true;
}

// Count the number of points STRICTLY inside the convex polygon
int p_inside(const std::vector&lt;std::pair&lt;int, int&gt;&gt;&amp; convex_polygon, const std::vector&lt;std::pair&lt;int, int&gt;&gt;&amp; points)
{
    int count = 0;
    for(auto point : points)
    {
        bool inside = is_inside(convex_polygon, point);
        if(inside)
        {
            count++;
        }
    }
    return count;
}

// Main
int main()
{
    int k, n;
    std::cin &gt;&gt; k &gt;&gt; n;
    std::vector&lt;std::pair&lt;int, int&gt;&gt; convex_polygon(k);
    std::vector&lt;std::pair&lt;int, int&gt;&gt; points(n);
    for(size_t i = 0; i &lt; convex_polygon.size(); i++)
    {
        int x, y;
        std::cin &gt;&gt; x &gt;&gt; y;
        convex_polygon[i] = {x, y};
    }
    bool convex = is_convex(convex_polygon);
    if(!convex)
    {
        std::cout &lt;&lt; "Input not convex...Exiting" &lt;&lt; std::endl;
        return 0;
    }

    for(size_t i = 0; i &lt; points.size(); i++)
    {
        int x, y;
        std::cin &gt;&gt; x &gt;&gt; y;
        points[i] = {x, y};
    }

    int count = p_inside(convex_polygon, points);
    std::cout &lt;&lt; "Points inside: " &lt;&lt; count &lt;&lt; std::endl;
    return 0;
}


1) Should std::pair be passed as reference? Is there an exact criteria to see if a given object is large enough to be passed as reference?

2) Is the use of const correct? 

3) What other improvements can be made?

4) I am planning to test it extensively using Catch2 framework. I am learning this framework myself. What suggestions do you have to maintain professional test quality?
Data types


Why not use a simple point struct instead of std::pair&lt;int, int&gt;? It doesn't have to do anything, just a simple one would suffice:

struct point {
    int x = 0;
    int y = 0;
};


This would increase readability and generally might make the code more bug resistent. Remember, std::pair&lt;int, int&gt; can represent many different things: points, vectors, health + mana points, entry in a std::map&lt;int, int&gt; (which by itself can have many different meanings), exchange rate of apples for oranges, ...

Using a concrete type prevents that kind of confusion.
Similarly, one could make a type alias polygon for std::vector&lt;point&gt;, like

using polygon = std::vector&lt;point&gt;;



  A more advanced implementation could instead take a polygon as a range of points (= a pair of iterators), or use its own polygon class.



perdot


The name doesn't match what it actually does. Yes, the perpendicular dot product is used internally, but the returned value isn't the result of it. The returned value only indicates whether the point is left of, right of or on the line - and the function name should reflect that, e.g. something like determine_side.
The return values seem kinda arbitrary. Why not use an enum instead, like

enum class side {
    left,
    right,
    center
};

The order of the parameters seems kind of arbitrary and unintuitive. Why do the points of the "line" have to be passed as first and third parameter? With a simple help from the type system, this could be clarified a lot by introducing a small line helper struct:

struct line {
    point from;
    point to;
};



Putting all those fixes together (and refactoring the perpendicular dot product into its own helper function), we get:

int perpendicular_dot_product(point a, point b, point c) noexcept {
    const auto ab_x = b.x - a.x;
    const auto ab_y = b.y - a.y;
    const auto ac_x = c.x - a.x;
    const auto ac_y = c.y - a.y;

    return ab_x * ac_y - ab_y * ac_x;
}


side determine_side(line l, point p) noexcept {
    const auto per_dot = perpendicular_dot_product(l.from, p, l.to);

    if(per_dot &lt; 0)
    {
        return side::right;
    }
    else if(per_dot &gt; 0)
    {
        return side::left;
    }

    return side::center;
}


Much nicer to read and much clearer in its intent, right?

is_convex


Bug: If n &lt;= 2 then the code likely doesn't work as intended, and might even access out of bounds memory. Please add checks for those cases.


  Now the question becomes: What should happen in those cases? Always return false, or throw an exception?
  
  I think always returning false would be better in this case, since it is just a query whether the contained data set conforms to some criteria. YMMV.

Also, there is another edge case if all points in convex_polygon are on a line. Currently, is_convex returns true for that case, but is this intended? I wouldn't assume so.


Other than that, it seems to be working fine. It would need some adjustments for the changes mentioned above, though, and could be slightly simplified.

bool is_convex(const polygon&amp; convex_polygon) noexcept
{
    const auto n = convex_polygon.size();
    if(n &lt;= 2) return false;

    auto sense = side::center;

    for(auto i = 0u; i &lt; n; ++i)
    {
        auto new_sense = determine_side(line{convex_polygon[i], convex_polygon[(i + 2) % n]}, convex_polygon[(i + 1) % n]);

        if(sense == side::center)
        {
            sense = new_sense;
        }
        else if(new_sense != side::center &amp;&amp; new_sense != sense)
        {
            return false;
        }
    }

    return sense != side::center;
}


is_inside

Not much to do here, other than adjusting for above changes and some slight simplification.

bool is_inside(const polygon&amp; convex_polygon, const point p) noexcept
{
    const auto n = convex_polygon.size();

    const auto sense = determine_side(line{convex_polygon[n - 1], convex_polygon[0]}, p);
    if(sense == side::center)
    {
        return false;
    }

    for(auto i = 0u; i + 1 &lt; n; ++i)
    {
        auto new_sense = determine_side(line{convex_polygon[i], convex_polygon[i + 1]}, p);

        if(new_sense != sense)
        {
            return false;
        }
    }
    return true;
}


p_inside

Again, the name is weird: Why not use count_points_inside?

Other than that, the logic seems fine. It could however easily be simplified using an algorithm provided by the standard library: std::count_if (inside header &lt;algorithm&gt;).

int count_points_inside(const polygon&amp; convex_polygon, const std::vector&lt;point&gt;&amp; points)
{
    return std::count_if(std::begin(points), std::end(points), [&amp;](auto p) { return is_inside(convex_polygon, p); });
}



  Note how I didn't replace the type of points with polygon and used a std::vector&lt;point&gt; instead, since (at least for the human reader) there is a semantic difference between a polygon and a set of points.
  
  A better version would takes points as a range of points instead:

template&lt;typename Iter, typename = std::enable_if_t&lt;std::is_same_v&lt;point, typename std::iterator_traits&lt;Iter&gt;::value_type&gt;&gt;
int count_points_inside(const polygon&amp; convex_polygon, Iter first, Iter last)
{
    return std::count_if(first, last, [&amp;](auto p) { return is_inside(convex_polygon, p); });
}

  
  (The typename = std::enable_if_t&lt;...&gt; part is only there to verify that the passed iterators point to points. The code would work without that.)


main


Errors should be printed to std::cerr instead of std::cout.
Some better instructions for the user would be nice. Currently, the user only ever gets notified if something goes wrong and thus has no clue what actually is expected of him.
The entering procedures of convex_polygon and points could be refactored out into a helper function, since the logic overlaps quite a lot.
In the error case, a different return value should be used, like 1 (or EXIT_FAILURE from the &lt;cstdlib&gt; header, to be more descriptive) in order to indicate that the program didn't execute as planned.
The final return 0; statement could be removed, as the compiler will autogenerate that one. (If it isn't removed, EXIT_SUCCESS could be returned instead as a more descriptive value).


Q &amp; A


Generally, I try to pass everything but containers (including classes that contain containers as data members) and non-copyable types by value as default. I only switch to references if I either know that the type is very large, or performance measurements show that passing by reference is a performance benefit.

If in doubt, measure.
const is used well for function parameters. However, local variables that aren't being changed can also benefit from being marked const (see snippets above, e.g. for perpendicular_dot_product).
See above. Other than that, some functions like perpendicular_dot_product or determine_side could be made constexpr, as esote mentions in his answer. This would allow the compiler to precalculate those calls at compile time if the values are known.
I'd suggest trying test-driven development (i.e. write test before writing the actual implementation). Other than that, know your edge cases, and test those specifically (that way, you're unlikely to get bugs like the ones in is_convex).