"Tower counting" gives correct output, but CodeChef says "wrong answer", maybe there's a problem with corner case but i cant figure out

Question

here's the question:

Flappy Bird is on a screen with height H pixels (a 2D plane where the y-axis corresponds to the vertical direction). There are N vertical obstacles in the room (numbered 1 through N); for each valid i, the coordinates of the endpoint of the i-th obstacle are (xi,ai). There are two types of obstacles:

Type 0: A line segment between the points (xi,0) and (xi,ai), i.e. upwards from the floor.

Type 1: A line segment between the points (xi,H) and (xi,ai), i.e. downwards from the ceiling.

For each obstacle, you need to find the number of endpoints of other obstacles (not including itself) that are visible from its endpoint. Two endpoints are visible from each other if the line segment joining them does not intersect or touch any other obstacle. Note that each obstacle has exactly one endpoint

Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers H and N. The following N lines describe the obstacles. For each valid i, the i-th of these lines contains three space-separated integers ti, xi and ai, where ti is the type of the i-th obstacle.

Output:

For each test case, print a single line containing N space-separated integers. For each valid i, the i-th of these integers should be the number of endpoints visible from the i-th endpoint.

Constraints:

1. 1 ≤ T ≤ 200
2. 1 ≤ H ≤ 10^9
3. 1 ≤ N ≤ 2000
4. ti ∈ {0,1} for each valid i
5. 1 ≤ xi ≤ 10^9 for each valid i
6. 1 ≤ ai ≤ H−1 for each valid i
7. no two obstacles touch or intersect
8. the sum of N over all test cases does not exceed 20,000

code:

#include <stdio.h>
#include <math.h>



int main (void)
{
    int T;
    scanf("%d",&T);
    if (!(T > 0 && T <= 200))
    {
        return(0);
    }

  int sum_N = 0; //it must not exceed 20000;

    for (int t = 0; t < T; ++t)
   {
        int H;        //height 
        scanf("%d",&H);
        if (!(H > 0 && H <= 1000000000))
        {
            return(0);
        }

      int N;          // no of obstacles
      scanf("%d",&N);
      if (!(N > 0 && N <= 2000))
      {
        return(0);
      }

      sum_N += N;
      if (sum_N > 20000)     // constrain given in que
      {
        return 0;
      }

      if (H ==1)          //special case for H == 1
      {
          for (int i = 0; i< N ; i++)
          {
              printf("0");
              if (i != N-1)
              {
                  printf(" ");
              }
          }
          continue;
      }
      int visible[N];       //how many blocks are visible from I the block
      for (int r = 0; r<N;++r)
          {
              visible[r] = 0;
          }

      int obst[N][3];
      // N O == UPPPER/LOWER
      // N 1 == X COORDINATE
      // N 2 == Y COORDINATE


      for (int n = 0; n < N; ++n)
      {

          scanf("%d %d %d",&obst[n][0],&obst[n][1],&obst[n][2]);
          if(obst[n][0] != (1) && obst[n][0] != (0) )
          {
              return (0);
          }
          if (!(obst[n][1] > 0 && obst[n][1] <= 1000000000))
          {
            return(0);
          }
          if (!(obst[n][2] > 0 && obst[n][2] <= H -1))
          {
            return(0);
          }

      }

      // sorting based on X coordinate
      for (int i = 0; i <N ; i++)
      {
        int swapped = 0;
        for (int j = 0;j < N-1 ;j++)
        {
          if (obst[j][1] > obst[j+1][1])
          {
            //swap
            int temp = obst[j][1];
            obst[j][1] = obst[j][2];
            obst[j][2] = temp;
            swapped++;
          }
        }
        if (swapped == 0)
        {
          break;
        }
      }

      //checking that objects don't intersect

      for (int i = 0; i<N;++i)
      {
        for (int j = 0; j <N && i!= j ;++j)
        {
          if (obst[i][1] == obst[j][1])      //if X coordinate is same
          {
            if (obst[i][0] == obst[j][0])   //if they are both upper/lower
            {
              return 0;
            }
            else      // if both are different then height must be less than H
            {
              if (obst[i][0] == 0)
              {
                if (obst[i][2] - obst[j][2] > 0) // xi - (H -xj) <= H 
                {
                  return 0;
                }
              }
              else
              {
                if (obst[j][2] - obst[i][2] > 0)    //xj - (H -xi) <= H 
                {
                  return 0;
                }
              }
            }
          }
        }
      }






      // selecting one obstiacle and checking for it
      for (int i = 0; i < N; ++i)
      {
          int j = 0;
          while(j<N)
          {
                if(i == j)
                {
                    goto next;
                }
              //checking if any obst btw them is in line of sight
              int k;
              int max_k;

              if (i < j)
              {
                   k = i+1;
                   max_k = j;
              }
              else
              {
                   k = j+1;
                   max_k = i;
              }
                  int notvisible = 0;
                  for (; k < max_k ; ++k)
                  {
                        double xi = obst[i][1];
                        double yi = obst[i][2];
                        double xj = obst[j][1];
                        double yj = obst[j][2];
                        double xk = obst[k][1];
                        double yk = obst[k][2];
                        double y_touch = yi + ((yj-yi)*(xk-xi)/(xj-xi));

                      if ( obst[k][0] == 0)
                      {
                          if (y_touch <= yk)
                          {
                              notvisible++;
                              break;
                          }
                      }

                      if ( obst[k][0] == 1)
                      {

                          if (y_touch >= yk)
                          {
                              notvisible++;
                              break;
                          }
                      }

                  }
                  //if breaks comes here
                  if (notvisible == 0)
                  {
                      visible[i]++;
                  }
                //iterating j
                next:
                ++j;
          }
      }

      //print answers
      for (int gg = 0; gg<N;gg++)
      {
          printf("%d",visible[gg]);
          if ( gg != N-1)
          {
              printf(" ");
          }
      }
      printf("\n");
  }

    return 0;
}

Example Input

1
10 4
0 2 5
1 5 6
1 8 8
0 11 2

Example Output

2 3 2 3

and that's what I get, maybe there's a problem with corner cases but I can't figure out which.

Answer 1

... it works any test case I throw at it, but codechef shows that its wrong answer

Well, I can spot at least one test case that will fail.

Try this

1
100 3
0 10 20
0 1 5
1 10 80

This should give the output:

2 2 2

but your code doesn't give that result.

The above input give this picture:

where the red lines are the obstacles and the blue arrows shows which obstacles can be seen from a specific obstable.

The problem with your code is that it doesn't handle the situation where there are two obstacles at the same X coordinate, i.e. on upwards from the floor and the other downwards from the ceiling. This is perfectly legal according to the constraints.

But your code is:

double y_touch = yi + ((yj-yi)*(xk-xi)/(xj-xi));
                                        ^^^^^^

so when xj and xi are the same, you have a division by zero.

In other words - you need to handle xj == xi as a special case.