WA in SICRANO http://www.spoj.pl/problems/SICRANO/

[shashank_mnnit14]

i am solving spoj.pl/problems/SICRANO/
[color=#FF0000]I think in this question all we need to do is check the slope of point (to be checked) with intial point of segment ,also checking checking whether that point lies between segment or not.. and if slope is same as of SEGMENT>> it lies on segement .[/color]
IS LOGIC CORRECT ???

here is my code in C++ using the same logic ???

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int t,i,n,m,k,count;
scanf("%d",&t);
        while(t--)
        {
                double elev;
                count=0;
                scanf("%d %d",&n,&m);
                int px[n],py[n];
                for(i=0;i<n;i++)
                        scanf("%d %d",&px[i],&py[i]);
                int sx1[m],sy1[m],sx2[m],sy2[m];
                double slope[m];
                for(i=0;i<m;i++)
                {
                        scanf("%d %d %d %d",&sx1[i],&sy1[i],&sx2[i],&sy2[i]);
                        slope[i]=(((double)sy2[i]-(double)sy1[i])/((double)sx2[i]-(double)sx1[i]));
                }
                for(k=0;k<m;k++)
                {
                        count=0;
                        for(i=0;i<n;i++)
                        {
                                elev=0.0;
                                if((sx1[k]<=px[i])&&(px[i]<=sx2[k])&&((sy1[k]<=py[i])&&(py[i]<=sy2[k])))
                                {
                                        if((sy1[k]==py[i])&&(sx1[k]==px[i]))
                                        count++;
                                        else
                                        {
                                                elev+=(((double)sy1[k]-(double)py[i])/((double)sx1[k]-(double)px[i]));
                                                if(elev==slope[k])
                                                        count++;
                                        }
                                }
                        }
                        printf("%d\n",count);
                }
        }
return 0;
}

checked on many .. even with infinity cases!!! still WA
please help !!!

[jnsvipin]

Are u sure infinite cases? Y axis too where ur slope is different?
I guess u got ur mistake
try this ..
1

4 5

0 3
2 2
3 3
4 4

0 0 5 5
3 3 4 4
0 0 1 0
0 0 0 1
0 0 0 5

[shankarigiri]

Hello, Here is my code........Can any one tell me why am i getting wrong answer?
even though it gives right answers for the sample test case and the one posted here.......? pls...........

#include<stdio.h>
int main()
{
    int nt,i,n,m,j,x1,x2,y1,y2,xt,yt;
    scanf("%d",&nt);
    for(i=0;i<nt;i++)
    {
                     scanf("%d %d",&n,&m);
                     int x[n],y[n];int out[m],k=0,l=0;
                     for(j=0;j<n;j++)
                     {
                                     scanf("%d %d",&x[j],&y[j]);
                                     }
                     for(j=0;j<m;j++)
                     {
                                     scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                                     int lhs,rhs;
                                     lhs=(xt-x1)*(y2-y1);
                                     rhs=(yt-y1)*(x2-x1);
                                     int cnt=0;
                                     for(l=0;l<n;l++)
                                     {
                                                     if(x[l]>=x1 && y[l]>=y1 && x[l]<=x2 && y[l]<=y2)
                                                     {
                                                     if(((x[l]-x1)*(y2-y1))==((y[l]-y1)*(x2-x1)))
                                                                 cnt++;
                                                                 }
                                                                 }
                                     out[j]=cnt;
                                     }
                     for(j=0;j<m;j++)
                     {
                                     printf("%d\n",out[j]);
                                     }
                                     }
    getch();
}

[leppyr64]

You are performing calculations with uninitialized variables.

[shankarigiri]

Ok sir......I tried initializing all the variables to zero........Still getting wrong answer sir............

[leppyr64]

Post your updated code.

[shankarigiri]

here is my code sir......

#include<stdio.h>
int main()
{
    int nt=0,i=0,n=0,m=0,j=0,x1=0,x2=0,y1=0,y2=0,xt=0,yt=0;
    scanf("%d",&nt);
    for(i=0;i<nt;i++)
    {
                     scanf("%d %d",&n,&m);
                     int x[n],y[n];int out[m],k=0,l=0;
                     for(j=0;j<n;j++)
                     {
                                     scanf("%d %d",&x[j],&y[j]);
                                     }
                     for(j=0;j<m;j++)
                     {
                                     scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                                     int lhs=0,rhs=0;
                                     lhs=(xt-x1)*(y2-y1);
                                     rhs=(yt-y1)*(x2-x1);
                                     int cnt=0;
                                     for(l=0;l<n;l++)
                                     {
                                                     if(x[l]>=x1 && y[l]>=y1 && x[l]<=x2 && y[l]<=y2)
                                                     {
                                                     if(((x[l]-x1)*(y2-y1))==((y[l]-y1)*(x2-x1)))
                                                                 cnt++;
                                                                 }
                                                                 }
                                     out[j]=cnt;
                                     }
                     for(j=0;j<m;j++)
                     {
                                     printf("%d\n",out[j]);
                                     }
                                    }
          return 0;
          }

[leppyr64]

Your issue lies mainly in this line of code:
if(x[l]>=x1 && y[l]>=y1 && x[l]<=x2 && y[l]<=y2)

[TLE__sof]

sir i am getting correct aswer for test case and the case given in forum but WA when i submit it at spoj.
dont know why.
[

[leppyr64]

Your issue is almost 100% identical to the poster above...
if(a[j]>=x1[i]&&a[j]<=x2[i])

[TLE__sof]

if((a[j]>=x1[i]&&a[j]<=x2[i])||(a[j]<=x1[i]&&a[j]>=x2[i]))

this is also giving wrong answer

but why?
coordinates are positive only not negative so i shouold not consider the negative case

[leppyr64]

You are making an assumption about the input data.

[TLE__sof]

ok i read it again .
coordinated of segment can be -ve bt of points are +ve.i am right?
i changed code but getting wrong only.

if 2nd x coordinate is -ve i have interchanged both points of segment

[leppyr64]

Your issue is almost 100% identical to the poster above...
if(a[j]>=x1[i]&&a[j]<=x2[i])

It's not a matter of positive or negative. If all of the variables in this if statement are positive it still has the same issue.

[TLE__sof]

u want to say that 5 5 0 0 can be input so

if(1>=5 && 1<=0)

will be false.
i have considered this case also in below code.

[leppyr64]

Your algorithm is not accurate. You have not considered all possibilities.

[pv1]

code removed got ac

[TLE__sof]

the ques. is very easy and shorter in code length.

[pv1]

kkkkk......i wil code with a new approach but.....i just want 2 know what is wrong with this approach......inspite it is lengthy i want 2 know where do i fail......???

[leppyr64]

The biggest issue is that you are assuming that the slope will be an integer value. As mentioned before you should abandon this solution and simplify it greatly. Work with a pen and paper for a while and find a better algorithm.