Click here to Skip to main content
15,912,400 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
Problem:
There are N points in the plane. The ith point has coordinates (xi, yi). Perform the following queries:
1) Reflect all points between point i and j both including along the X axis. This query is represented as "X i j"
2) Reflect all points between point i and j both including along the Y axis. This query is represented as "Y i j"
3) Count how many points between point i and j both including lie in each of the 4 quadrants. This query is represented as "C i j"

Input:
The first line contains N, the number of points. N lines follow.
The ith line contains xi and yi separated by a space.
The next line contains Q the number of queries. The next Q lines contain one query each, of one of the above forms.
All indices are 1 indexed.

Output:
Output one line for each query of the type "C i j". The corresponding line contains 4 integers; the number of points having indices in the range [i..j] in the 1st,2nd,3rd and 4th quadrants respectively.

Constraints:
1 <= N <= 100000
1 <= Q <= 1000000
You may assume that no point lies on the X or the Y axis.
All (xi,yi) will fit in a 32-bit signed integer
In all queries, 1 <=i <=j <=N

Sample Input:
4 // number of points
1 1
-1 1
-1 -1
1 -1
5//number of operations
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3

Sample Output:
1 1 1 1
1 1 0 0
0 2 0 1

My solution is working for small inputs, but it is not working for 100000points and at the time of execution getting segmentation fault for above 100000 points.
C++
#include<stdio.h>               
  int main()
  {
  
 //int* a;
//a=(int *)malloc(1000);
  int a[1000][1000],c,d,n,i,j,q1=0,q2=0,q3=0,q4=0,will=1,b[20][20],k=0;
  char p;
  //printf("enter the number of co ordinate");
  scanf("%d",&n);
  for(i=0;i<n;i++)>
  for(j=0;j<2;j++)
  scanf("%d",&a[i][j]);
  void quadrant(int temp1,int temp2)
  {
                   
         if(temp1>=0&&temp2>=0)
        q1++;
      else if(temp1>=0&&temp2<=0)
        q2++;
      else if(temp1<0&&temp2<0)
        q3++;
      else if(temp1<=0&&temp2>=0)
         q4++;
 
   }
//printf("enter no of operations");
scanf("%d",&will);
                
while(will>0)
{

p=getchar();
scanf("%c",&p);
switch(p)
{
case 'x': 
                scanf("%d %d",&c,&d);
                  for(i=c-1;i<d;i++)>
                  a[i][1]=-(a[i][1]);break;
case 'y': 
                scanf("%d %d",&c,&d);
                for(i=c-1;i<d;i++)>
                a[i][0]=-(a[i][0]);break;
case 'c':       scanf("%d %d",&c,&d);
                for(i=0;i<=n-1;i++)
                {
                 int temp1,temp2;
                 temp1=a[i][0];
                 temp2=a[i][1];
              
                 quadrant(temp1,temp2);
                } 
               b[k][0]=q1;
               b[k][1]=q2 ;
               b[k][2]=q3;
               b[k][3]=q4; 
             
                  k=k+1; 
    q1=0;
    q2=0;
    q3=0;
    q4=0; 

                 
                  break;
case 'p':   printf(" the co-ordinates are:\n");
               for(i=0;i<n;i++)>
               {
                 for(j=0;j<2;j++)
                {
              printf("%d   ",a[i][j]);
                 }
                printf("\n");
                 } 
                 break;                               
     
default: printf("enter the correct choice\n");break;
}
if(will==1)
for(i=0;i<k;i++)>
{
printf("%d %d %d %d\n",b[i][0],b[i][1],b[i][2],b[i][3]);

}
will--;
}
}
Posted
Updated 5-Sep-11 18:36pm
v4

1 solution

You size "a" as
int a[1000][1000],

yet you only use a[i,0] and a[i,1]. So, you have a lot of wasted elements in the 2nd dimension of a (2..999).

Also, if your index into a goes beyond 1000, you're going to clobber memory or go way out of bounds. So, if your 100,000 is used to fill "a", you're hosed.

Also, I don't know what your input data is but you also dimension the "b" array at 20x20 but only use, in the 2nd dimension 0,1,2,3. And I don't know what the switch case "c" does but it has the potential for overflowing the 1st dimension of "b", depending on how large "k" gets.

I think you need to look closely at your use of the "a" and "b" double dimension arrays as the cause of your segmentation fault.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900