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.
#include<stdio.h>
int main()
{
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;
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++;
}
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--;
}
}