Given a set of points and pairs of lines, count the number of points that are between the pairs of lines

Question

This is a contest problem. The entire description is here.

In resume:

The question gives a point simulating a light explosion that always has a negative x coordinate, a set of pairs line segments on the y axis are given simulating walls and a set of points with positive x coordinate representing possible positions for a soldier.

The walls block the light forming a cone with low profile. So, in how many of the given points its possible for the soldier stay in low profile? (A point that stays exactly in the cone line is not valid)

Here is a image describing what I want to say:

The points g3 and g1 are not valid.

The input description:

The first line contains an integer T (T = 100) indicating the number of test cases.

In the first line of each case there will be the coordinate (x, y) of the explosion epicenter. The next line will contain an integer P (1 ≤ P), indicating the number of walls. The next P lines there will be pairs of integers indicating the position of the walls, the start and end of a wall (remember that they stay in the Y axis, it is, X = 0). Then there will be an integer G (G ≤ 10^4) indicating the points that are candidates to a hide place. Then G lines will follow with pairs of coordinates (x, y) indicating their coordinates.

All the coordinates will be between -10^4 and 10^4 and will be integers. The epicenter of the explosion will have X < 0 and the hides positions X > 0. The initial Y of a wall will be strictly less than its end. The walls will not be sorted. The walls won't overlap each other, nor share endpoints. There might be some repeated Goemon positions.

My solution test for each point if it is inside of the cone formed by a wall (if the point is above one line and below other line).

The problem is that this solution is too slow, resulting in time limit exceeded. How can I optimize it?

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef struct _point{
    int x,y;
    _point():x(0),y(0){}
    _point(int _x,int _y):x(_x),y(_y){}
}point_t;

typedef struct _line{
    point_t p1,p2;
    _line() : p1(0,0),p2(0,0){}
    _line(int y1,int y2) : p1(0,y1),p2(0,y2){}
}line_t;

inline int cross(point_t &a, point_t &b,point_t &c){
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

inline bool hasSameSign(int a,int b){
    return (a<0) == (b<0);
}


int main(void){
    int t;
    scanf("%d",&t);
    
    for (int i = 0,p,g,valid; i < t; ++i) {
        //read explosion coords
        int x,y;
        scanf("%d %d",&x,&y);
        point_t exps(x,y);
        
        //read initial and end points for each wall
        scanf("%d",&p);
        line_t *wall = new line_t[p];
        for (int j = 0; j < p; ++j)
            scanf("%d %d",&wall[j].p1.y,&wall[j].p2.y);
        
        //read all possible positions
        scanf("%d",&g);
        point_t *pos = new point_t[g];
        for (int j = 0; j < g; ++j)
           scanf("%d %d",&pos[j].x,&pos[j].y);
        
        //for each possible position and walls
        valid = 0;
        for (int k = 0; k < g; ++k) {
            for (int j = 0,signal1,signal2; j < p; ++j) {
                signal1 = cross(exps,wall[j].p1,pos[k]);
                signal2 = cross(exps,wall[j].p2,pos[k]);
                
                if(!hasSameSign(signal1, signal2)){
                    ++valid;
                    break;
                }
                
                //printf("%d %d\n",sinal1,sinal2);
            }
        }
        
        printf("%d\n",valid);
        delete [] wall;
        delete [] pos;
    }
}

Answer 1

You can get the intersection of a line described by 2 points with the y axis pretty easily using a simple formula.

First you sort the walls in increasing order. O(P log P)

For each point g you can get the intersection between the line g-E and x = 0 with g' = (g-E) / ((0-E.x) / (g.x-E.x)) + E (will need floating point operations) and you can search for g'.y in the walls array with a binary search. O(G log P)

---

Beyond that some comments about your code:

• using namespace std; is usually a warning sign. This has several issues. Instead only use it to pull in specific thing you actually use or limit it to function scope.

• Everything is in main. Reading the problem I'd expect a few functions like main, doSingleTest, readWalls and processPoints.

• Declaring additional variables in the for initializer. This is very odd to see. Give each of them their own line in the body:

  for (int j = 0; j < p; ++j) {
      //j can stay because it's the iterator value
  
      // you calculate them immediately after so join the declaration with initialization
      int signal1 = cross(exps,wall[j].p1,pos[k]);
      int signal2 = cross(exps,wall[j].p2,pos[k]);
  

• Raw array usage. Instead use vector which will auto clean up when it goes out of scope.

Answer 2

Algorithm

Let all the walls be defined by \$w_k\$ for the low position of wall \$k\$ and \$W_k\$ for the high position of wall \$k\$.

To check if the point \$G_i\$ is in cover the point should be projected onto the Y-axis along the line through \$G_i\$ and \$E\$. Then see if it is inside of any of the walls.

We take the line between the points using the straight line equation and solve for the coefficients: \$y = kx+m\$ inserting coordinates for \$G_i\$ and \$E\$ yields two equations:

$$E_y = kE_x+m$$ $$G_{iy} = kG_{ix}+m$$

Subtract the lower from the upper: $$E_y - G_{iy} = (E_x - G_{ix})k \Leftrightarrow k = \frac{E_y - G_{iy}}{E_x - G_{ix}}$$ inserting \$k\$ into the first equation yields: $$E_y = \frac{E_y - G_{iy}}{E_x - G_{ix}}E_x+m \Leftrightarrow m = E_y - \frac{E_y - G_{iy}}{E_x - G_{ix}}E_x$$ or put on a common divisor: $$m = \frac{(E_x - G_{ix})Ey - (E_y - G_{iy})Ex}{E_x - G_{ix}} = \frac{ G_{iy}Ex- G_{ix}Ey}{E_x - G_{ix}}$$

Recall the straight line equation: \$y = kx+m\$ we want the projection onto \$x=0\$ so \$y=m\$ for \$G_i\$ projected onto the Y-axis. I.e. the point is safe if for any \$k\$ the following holds:

$$w_k < m < W_k$$

At this point we could calculate the above \$m\$ using floating point numbers and convert all the wall positions to floating point too. But we introduce errors, errors that might give the wrong answer if the point is exactly on a wall (which should be unsafe).

Let \$a = E_x - G_{ix}\$ and \$b=G_{iy}Ex- G_{ix}Ey\$ so that we get: $$w_k < \frac{b}{a} < W_k$$

To get rid of the division we will multiply through by \$a\$ but need to take care to flip the inequalities if \$a<0\$, so we get:

$$\begin{align}w_ka < b < W_ka \qquad& for\quad a \ge 0\\w_ka > b > W_ka \qquad& for\quad a < 0\end{align}$$

But recall that in the problem description it is said that \$E_x < 0\$ and \$G_{ix} > 0\$ which means that \$a < 0\$ always. Thus we can simply use:

$$w_ka > b > W_ka$$

Now we can implement the solution using only integer arithmetic.

Implementing

This is some pseudo c++ code for implementation (I have a fewer so I make no guarantees on correctness here).

vector<pair<int, int>> walls; // Pair is (lower, higher) wall.
// ... read walls from input here ...
sort(walls.begin(), walls.end(), by_first_ascending); // implement comparator


for each point{
    int a = ...; // Calculate a as above
    int b = ...; // Calculate b as above

    // Using binary search, find the the first wall that
    // has it's starting point strictly above our projected y-position.
    auto wall = std::upper_bound(walls.begin(), walls.end(),
                    [a](pair<int,int>& w, int b){
                        return w.first*a > b;
                    });

    if (wall == walls.begin()){
        // Below first wall, not safe
    }
    else{
        // The current wall starts above us, so we back one down to get
        // (possibly) inside the previous wall (also handles wall==end()):
        --wall;

        // Wall can now not be end() and is safe to dereference.
        if ( wall->first*a > b && b > wall->second*a){
            // Point is in safe cover
        }
        else{
            // Point is not safe
        }
    }
}

The above implementation has \$\mathcal{O}(n\log k + k\log k)\$ time complexity where \$n\$ is the number of points and \$k\$ is the number of walls. The implementation also has high data locality.

Answer 3

I see a number of things that may help you improve your code. First, I'll analyze your code, and then explain a different algorithm and implementation that should be much faster.

When compiling C++, write C++

Most of this code is plain C that just happens to have been run through a C++ compiler. Your code would be much easier to read and much simpler, if you use C++. For example, the typedef struct form is completely unnecessary in C++.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. It isn't necessarily wrong to use, but be aware of when you absolutely shouldn't do it (such as in header files).

Avoid scanf if you can

There are so many well known problems with scanf that you're usually better off avoiding it. The usual approach is to read in user input into a string and then parse from there, in this case using something like atoi().

Avoid new and delete

Modern C++ has much less reason to use new and delete than in the past. For this particular problem, it can be avoided entirely as I'll show later on.

Rethink your algorithm

Each potential test point \$G\$ describes a ray between the explosion epicenter \$E\$ and itself. The \$y\$-intercept of that ray either intersects with a wall or not. If it does, the point is "safe", otherwise not. Since the \$y\$-intercept of any line of the form \$y = mx + b\$ is \$(0, b)\$, all that is required is to calculate \$b\$ and then see if there's a wall segment there or not. First, some elementary algebra: $$ y = mx + b $$ $$ b = y - mx $$ $$ m = \frac{G_y - E_y}{G_x - E_x} $$ $$ b = y - \frac{G_y - E_y}{G_x - E_x} x $$ We could substitute either end's \$x\$ and \$y\$ values in here to solve the equation. Let's arbitrarily choose point \$E\$. $$ b = E_y - \frac{G_y - E_y}{G_x - E_x} E_x $$

We could go with this calculation and things would work just fine, but since there is only one \$E\$, we can do a little preprocessing. Specifically, we can shift the entire coordinate system down by \$E_y\$ by subtracting \$E_y\$ from every \$y\$-coordinate. This makes our equation even simpler: $$ b' = -\frac{G_y'}{G_x - E_x} E_x $$ $$ b' = \frac{G_y' E_x}{E_x - G_x} $$

I've labelled the coordinates \$b'\$ and \$G_y'\$ to signify that this is with the shifted coordinate system.

So for any vertical wall segment \$\overline{W} = (0, lo) (0, hi)\$, we need only check that \$lo < b < hi\$ or equivalently, \$lo' < b' < hi'\$.

Use standard data structures

The standard template library (STL) has a number of very useful data structures and for this particular problem, I'd choose std::set. We can maintain a set of wall segments and then quickly identify the wall segment which might be a candidate for intersection using std::set::upper_bound. By creating a Wall class that defines a comparison operator that looks at the hi part of a wall segment, we can use upper_bound directly. Here is a Wall class with all of the required properties:

class Wall 
{
public:
    Wall(float hi, float lo=0)
        : low_(lo), high_(hi) 
    {}
    bool operator<(const Wall &w) const { return high_ < w.high_; }
    friend class Explosion;
private:
    float low_;
    float high_;
};

Now all we need is a class to store the Wall segments and to do the calculation mentioned above:

class Explosion
{
public:
    Explosion() = delete;
    Explosion(float x, float y) 
        : explo_x(x), explo_y(y), walls{}
    {} 
    void addWall(float lo, float hi) { walls.emplace(Wall(hi-explo_y, lo-explo_y)); }
    bool isSafe(float x, float y) const {
        y -= explo_y;
        float bprime = (y*explo_x)/(explo_x-x);
        auto top = walls.upper_bound(Wall{bprime});
        return top != walls.end() && top->low_ < bprime;
    }
private:
    float explo_x, explo_y;
    std::set<Wall> walls;
};

A few things to note are that:

1. walls.emplace is used so that walls receives each freshly created Wall.
2. The coordinates are all shifted by -explo_y.
3. If no wall is found, the point is clearly not safe, so we can exit.

Test code

Here's sample code showing how it works with the data corresponding to the graph in your question:

#include <iostream>
#include <iomanip>
#include <set>

#define SHOW(X) std::cout << std::boolalpha << # X " = " << (X) << '\n';


int main()
{
    Explosion ex(-12, 12);
    ex.addWall(4,6);
    ex.addWall(10,12);
    SHOW(ex.isSafe(8, 2));
    SHOW(ex.isSafe(10, 10));
    SHOW(ex.isSafe(12, 14));
}

Sample output

ex.isSafe(8, 2) = false
ex.isSafe(10, 10) = true
ex.isSafe(12, 14) = false

I'll leave it to you to put the rest together.