Magikarp's blog

By Magikarp, 10 years ago, In English

Hi, please help me figure out where I went wrong.

problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=127

my code:

    #include<bits/stdc++.h>
    using namespace std;

    struct point
    {
        int x,y;
    };

    struct line
    {
        point p1,p2;
    };

    //checks if point q lies on line segment pr.
    bool onSegment(point p,point q,point r)
    {
        if(q.x<=max(p.x,r.x) && q.x>=min(p.x,r.x) && q.y<=max(p.y,r.y) && q.y>=min(p.y,r.y))
        {
            //cout<<p.x<<","<<p.y<<" "<<q.x<<","<<q.y<<" "<<r.x<<","<<r.y<<" lolololol"<<endl;
            return true;
        }

        return false;
    }

    int turn(point p,point q,point r)
    {
        int result=(r.x-q.x)*(p.y-q.y)-(r.y-q.y)*(p.x-q.x);
        if(result<0)return -1;//right
        if(result>0)return 1;//left
        return 0;//collinear
    }

    bool ccw(point p,point q,point r)
    {
       // cout<<"check "<<p.x<<","<<p.y<<" "<<q.x<<","<<q.y<<" "<<r.x<<","<<r.y<<"--> "<<turn(p,q,r)<<endl;
        return turn(p,q,r) ;
    }

    bool intersection(line line1,line line2)
    {
        int o1=ccw(line1.p1,line1.p2,line2.p1);
        int o2=ccw(line1.p1,line1.p2,line2.p2);
        int o3=ccw(line2.p1,line2.p2,line1.p1);
        int o4=ccw(line2.p1,line2.p2,line1.p2);
        if( o1 != o2 && o3 != o4)
            return 1;
        //special cases
        if(o1==0 && onSegment(line1.p1,line2.p1,line1.p2))
            return true;
        if(o2==0 && onSegment(line1.p1,line2.p2,line1.p2))
            return true;
        if(o3==0 && onSegment(line2.p1,line1.p1,line2.p2))
            return true;
        if(o4==0 && onSegment(line2.p1,line1.p2,line2.p2))
            return true;

        return false;
    }

    int main()
    {

        int n;
        cin>>n;
        while(n--)
        {

            point pp1,pp2,pp3,pp4,pp5,pp6;

            cin>> pp5.x >>pp5.y >>pp6.x >>pp6.y;
            cin>>pp1.x>>pp1.y>>pp3.x>>pp3.y;

            if(pp1.x>pp3.x)
            {
                pp1.x^=pp3.x^=pp1.x^=pp3.x;
            }
            if(pp1.y<pp3.y)
            {
                pp1.y^=pp3.y^=pp1.y^=pp3.y;
            }

            if(pp5.x>=pp1.x && pp5.x<= pp3.x && pp5.y>=pp3.y && pp5.y <=pp1.y)
            {
                cout<<"T"<<endl;continue;
            }


            pp2.x=pp1.x;
            pp2.y=pp3.y;
            pp4.x=pp3.x;
            pp4.y=pp1.y;


            line l1,l2,l3,l4,l5;

            l1.p1=pp1;            l1.p2=pp2;

            l2.p1=pp2;            l2.p2=pp3;

            l3.p1=pp3;            l3.p2=pp4;

            l4.p1=pp4;            l4.p2=pp1;

            l5.p1=pp5;            l5.p2=pp6;


            int result=intersection(l5,l1);
            if(result)
            {
                cout<<"T"<<endl;
                continue;
            }
            result=intersection(l5,l2);
            if(result)
            {
                cout<<"T"<<endl;
                continue;
            }
            result=intersection(l5,l3);
            if(result)
            {
                cout<<"T"<<endl;
                continue;
            }
            result=intersection(l5,l4);
            if(result)
            {
                cout<<"T"<<endl;
                continue;
            }

            cout<<"F"<<endl;

        }
        return 0;
    }

  • Vote: I like it
  • -5
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For input

5 2 6 2 4 4 7 1

Correct output is, T your code products F.

Image Hosted At MyspaceGens