Mar 2012
1 / 26
Mar 2012
Sep 2012
shashank_mnnit14
Mar '12

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 unamused
please help !!! cry

3 months later
jnsvipin
Jun '12

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
Jun '12

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
Jun '12

You are performing calculations with uninitialized variables.

shankarigiri
Jun '12

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

shankarigiri
Jun '12

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
Jun '12

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

1 month later
TLE__sof
Jul '12

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
Jul '12

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

TLE__sof
Aug '12

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

TLE__sof
Aug '12

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
Aug '12

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
Aug '12

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
Aug '12

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

pv1
Aug '12

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
Aug '12

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.