Sort by

recency

|

7 Discussions

|

  • + 0 comments

    I'm pretty sure my solution isn't the intended solution, but in C I managed to solve this by 1) using the ray-crossing algorithm, and 2) severely optimizing the logic that happens for each pair of point and edge to not use any "ifs" (beyond the relevant one for the "for" loop) and minimize number of operations per loop.

  • + 0 comments

    My favorite topic and very easy to solve . top astrologer in Melbourne

  • + 0 comments

    Can somebody please, provide an Editorial for this challenge ? I tried using the ray crossing algorithm, but only the sample test cases pass and the others Time Out ! Is there any other technique which can be applied ? Or can my code be optimised ?

    #include<iostream>
    
    #include<bits/stdc++.h>
    
    #define ll long long
    
     
    
    using namespace std;
    
     
    
    #define x first
    
    #define y second
    
    #define Point pair<int,int>
    
    #define INF 500000
    
     
    
    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))
    
            return true;
    
       
    
        return false;
    
    }
    
     
    
    int orientation(Point p,Point q,Point r){
    
       
    
        int o = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    
        
    
        if(o==0)   
    
            return 0;
    
       
    
        return (o > 0) ? 1: -1;
    
    }
    
     
    
    bool doesIntersect(Point p1,Point q1,Point p2,Point q2){
    
     
    
        int o1 = orientation(p1,q1,p2);
    
        int o2 = orientation(p1,q1,q2);
    
        int o3 = orientation(p2,q2,p1);
    
        int o4 = orientation(p2,q2,q1);
    
     
    
        if(o1!=o2  && o3!=o4)
    
            return true;
    
     
    
        if(o1==0 && onSegment(p1,p2,q1)) return true;
    
     
    
        if(o2==0 && onSegment(p1,q2,q1)) return true;
    
     
    
        if(o3==0 && onSegment(p2,p1,q2)) return true;
    
     
    
        if(o4==0 && onSegment(p2,q1,q2)) return true;
    
     
    
    return false;
    
     
    
    }
    
     
    
    bool isInside(Point Polygon[],int n,Point p){
    
        //cout<<"Flag"<<endl;
    
        if(n<3) return false;
    
     
    
        int i=0,next;
    
       
    
        ll count=0;
    
     
    
        Point extream = {INF,p.y};
    
     
    
        do{
    
            next = (i+1)%n;
    
     
    
            //cout<<(Polygon[i]==p)<<endl;
    
            if(Polygon[i]==p) return true;
    
            //cout<<Polygon[i].x<<";"<<Polygon[i].y<<" "<<Polygon[next].x<<";"<<Polygon[next].y<<endl;
    
            //cout<<Polygon[i].x<<";"<<Polygon[i].y<<" "<<p.x<<";"<<p.y<<endl;
    
            
    
            if(doesIntersect(Polygon[i],Polygon[next],p,extream)){
    
               
    
                if(orientation(Polygon[i],Polygon[next],p)==0){   
    
                    if(onSegment(Polygon[i],p,Polygon[next]))
    
                        return true;
    
                }else
                count++;
    
               
    
            }
    
            i=next;
    
        }while(i!=0);
    
     
    
        return (count%2!=0);
    
    }
    
     
    
    ll solve(Point set[],Point polygon[],int n,int m){ 
    
        ll count = 0;
    
        for(int i=0;i<n;i++){
    
            if(isInside(polygon,m,set[i])){
    
                count++;
    
                //cout<<set[i].x<<" "<<set[i].y<<endl;
    
            }
    
        }
    
     
    
        return count;
    
    }
    
     
    
    int main(){
    
       
    
        int n,q,m;
    
        cin>>n>>q;
    
     
    
        Point set[n];
    
       
    
        for(int i=0;i<n;i++)
    
            cin>>set[i].x>>set[i].y;
    
     
        Point polygon[20];
    
        while (q--)
    
        {
    
            /* code */
    
            cin>>m;
    
            for(int i=0;i<m;i++)
    
                cin>>polygon[i].x>>polygon[i].y;
    
            cout<<solve(set,polygon,n,m)<<endl;
    
        }
    
       
    
        return 0;
    
    }
    
  • + 1 comment

    Could someone please provide an editorial?

  • + 0 comments

    the test cases are not well prepared. I get all the test cases passed just by making brute-force search point by point.