问题描述
问题:
飞机上有N个点.第i个点的坐标为(xi，yi).执行以下查询:
1)反射点i和j之间的所有点，包括沿X轴的所有点.此查询表示为"X i j"
2)反射点i和j之间的所有点，包括沿Y轴.此查询表示为"Y i j"
3)计算在点i和点j之间都包含多少个点，分别位于4个象限中.此查询表示为"C i j"
输入:
第一行包含N，即点数. N行.
第i行包含xi和yi，中间用空格隔开.
下一行包含查询数量Q.接下来的Q行分别包含上述形式之一的一个查询.
所有索引均为1索引.
输出:
对于类型为"C i j"的每个查询，输出一行.对应的行包含4个整数；第一，第二，第三和第四象限中索引范围为[i..j]的点数.
约束:
1< = N< = 100000
1< = Q< = 1000000
您可以假设X轴或Y轴上都没有点.
所有(xi，yi)将适合32位有符号整数
在所有查询中，1< = i< = j< = N
样本输入:
4//点数
1 1
-1 1
-1 -1
1 -1
5//操作次数
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3
示例输出:
1 1 1 1
1 1 0 0
0 2 0 1
我的解决方案适用于较小的输入，但不适用于100000点，并且在执行时遇到高于100000点的分段错误.
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;
//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--;
}
}推荐答案
int a[1000][1000],
但您仅使用a [i，0]和a [i，1].因此，在(2..999)的第二维上有很多浪费的元素.
另外，如果您的索引超过1000，则将破坏内存或超出范围.因此，如果用您的100,000来填充"a"，那么您就被抽水了.
另外，我不知道您的输入数据是什么，但您也将"b"数组的尺寸设置为20x20，但只能在第二维0、1、2、3中使用.而且我不知道开关盒"c"的作用是什么，但它可能会溢出"b"的第一维，具体取决于"k"的大小.
我认为您需要仔细查看使用"a"和"b"二维数组作为细分错误的原因.
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.
这篇关于消除此程序中的分段错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！