191 WA , plizzzzzzzzzzzz help me

[naved92]

can anyone help me finding the bug????

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;


class Point{

public:
int x,y;
void input(int a,int b);

};


void Point:: input(int a,int b)
{  x=a;
   y=b;

return ;
}

int cross(Point pi,Point pj,Point pk)
{  int a,b;
//cout<<"calling cross"<<endl;
    a=(pk.x-pi.x)*(pj.y-pi.y);
    b=(pj.x-pi.x)*(pk.y-pi.y);
    return a-b;

}

bool onsegment(Point pi,Point pj,Point pk)
{
    int minx=min(pi.x,pj.x),maxx=max(pi.x,pj.x),miny=min(pi.y,pj.y),maxy=max(pi.y,pj.y);

    if((minx<=pk.x) && (pk.x<=maxx) && (miny<=pk.y) && (pk.y<=maxy)) return true;
    //cout<<minx<<maxx<<maxy<<miny;
    //if(minx<=pk.x &(pk.x<=maxx) )return true;
    else return false;


}
bool intersect(Point P1,Point P2,Point P3,Point P4)
 {int d1,d2,d3,d4;
    d1=cross(P3,P4,P1);
    //cout<<"d1"<<d1<<endl;

    d2=cross(P3,P4,P2);
    //cout<<"d2"<<d2<<endl;

    d3=cross(P1,P2,P3);
    //cout<<"d3"<<d3<<endl;
    d4=cross(P1,P2,P4);
    //cout<<"d4"<<d4<<endl;
    if((d1>0&&d2<0 || (d1<0&&d2>0) )&& ((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
    else if (d1==0 && onsegment(P3,P4,P1)) return true;
    else if(d2==0 && onsegment(P3,P4,P2))return true;
     else if(d3==0 && onsegment(P1,P2,P3))return true;
    else if(d4==0 &&onsegment(P1,P2,P4))return true;
    else return false;}


int main()
{  int tc,t=0;
cin>>tc;
    while(tc--){
    Point Ple,Pbe,P1,P2,P3,P4;
    int xle,yle,xbe,ybe,xleft,ytop,xright,ybottom;
    cin>>xle>>yle>>xbe>>ybe>>xleft>>ytop>>xright>>ybottom;

    Ple.input(xle,yle);
    Pbe.input(xbe,ybe);

     P1.input(xleft,ytop);
    P2.input(xleft,ybottom);
    P3.input(xright,ybottom);
    P4.input(xright,ytop);
   if(intersect(Ple,Pbe,P1,P2)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P2,P3)==true)cout<<"T"<<endl;
      else if (intersect(Ple,Pbe,P3,P4)==true)cout<<"T"<<endl;
   else if(intersect(Ple,Pbe,P4,P1)==true)cout<<"T"<<endl;
   else cout<<"F"<<endl;
   //cout<<"Case :"<<++t<<endl;
   }

    return 0;
}


[brianfry713]

Try the I/O in this thread.

[LifeMaker]

The trick is that: "The rectangle consists of four straight lines and the area in between." so the line segment can intersect with a the area of the rectangle, and not necessarily intersect with the one of the sides of the rectangle.

so, for this test case:

Code: Select all

1
1 1 2 2 0 4 4 0


the ouput is

Code: Select all

T