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

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. 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
#include
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 _li

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.

StackExchange Code Review Q#104143, answer score: 7