We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Geometry
  4. Polygon
  5. Discussions

Polygon

  • swithin_abner
     + 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;

}