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;
}
}