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;
    }

Full text and comments »

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

By Magikarp, 10 years ago, In English

Hi I am getting TLE in the 7th test case. How do I optimize my code? Problem link: http://www.spoj.com/problems/MATCHING/

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    #include<set>
    #include<cstring>

    using namespace std;

    #define in(a) scanf("%d",&a);
    #define pb push_back

    vector <int> G[50000+5];
    bool seen[50000+5];
    int matchL[50000+5],matchR[50000+5],A[50000+5];
    int n,m;

    bool bpm(int u)
    {
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(seen[v])
                continue;
            seen[v]=true;

            if(matchR[v]<0 || bpm( matchR[v] ))
            {
                matchR[v]=u;
                matchL[u]=v;
                return true;
            }


        }
        return false;
    }

    int main()
    {
        int n,m,p;
        set<int> row;
        set<int> col;
        set<int>::iterator it;

        int pos=0;
        in(n);in(m);in(p);
        while(p--)
        {
            int x,y;
            in(x);in(y);
            if(row.find(x)==row.end()){
                row.insert(x);
                A[pos++]=x;
            }


            G[x].pb(y);
        }

        /*for(int i=0;i<10;i++)
            cout<<A[i]<<" ";
        cout<<endl;*/

        memset(matchL,-1,sizeof(matchL));
        memset(matchR,-1,sizeof(matchR));


        m=row.size();
        //n=B.size();
        int cnt=0;

        for(int i=0;i<m;i++)
        {
            memset(seen,0,sizeof(seen));

                if( bpm( A[i] ) )
                    cnt++;

        }
        printf("%d\n",cnt);

        return 0;
    }

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By Magikarp, 10 years ago, In English

Hello all, I am trying to do this spoj problem, link: http://www.spoj.com/problems/CSTREET/ and here is what I have tried http://ideone.com/1jkKLl .

Please help me to figure out where I have made a mistake. Thanks!

Full text and comments »

Tags spoj, wa
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Magikarp, 11 years ago, In English

Hi all, This is the problem link: http://www.spoj.com/problems/ANARC05B/ my solution: http://ideone.com/irmtrP

Previously it was giving NZEC but after adding the try catch block it gives WA. I can't figure out what's going wrong. I have tried all the test cases available on the page(from the comments section) and got correct answer for all those test cases. Still I get WA. Please help me if there is anything that I missed out. Thanks.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Magikarp, 11 years ago, In English

Hi!

I am trying to solve this problem: http://www.spoj.com/problems/PT07Z/ . I am trying to find the diameter of the tree by using double BFS but I am getting TLE. Here is my code:

http://ideone.com/vC9vsd

Thank you.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it