The Delicious Cake

JUNE LONG CHALLENGE                                           Problem code: Contain



/*
Algorithm:-
  --> We will create concentric hulls as many as possible.
       This can be done using a tracking array to keep track of points which are still unused and passing.
       it again in convex hull function We will do this until our track array becomes empty.

Algorithm used :-
       Finding convex hull using graham scan in O(nlogn) ( For AC )
       Finding convex hull using jarvis march in O(n^2) ( For 35 points )

 --> Then we will memoize all these convex hulls.
       Now we cant create hulls for each query as it will result in  O(q*n^2) complexity (15 points).
       So what we will do is create a 2d vector of vectors (in simple words sort of adjacency list)
       Then we will process each query. We will check that our point x,y lies in how many convex polygons(layers) in O(q* no of layers).
       To check weather a point belongs  to a polygon on not i used a pointIsInPoly function which returns 1 if point lies on or inside the polygon thereafter i am checking for the existance of that point on boundary if it is on boundary i wont cosider it as candle must lie stricly inside a polygon.


          --Point detection algorithm used  :-

CODE IN CPP :

 */
#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<climits>
#include<set>

#define fio ios_base::sync_with_stdio(fals

e);
#define ll            long long int
#define ull           unsigned long long int
#define lld           long double
#define cinlld(x)     lld x;cin>>x;
#define cinll(x)      ll x;cin>>x;
#define cini(x)       int x;cin>>x;
#define cins(x)       string x;cin>>x;
#define vect(x)       vector<ll> x;
#define vect1(x)      vector<ll> x;x.push_back(0);
#define pb(x)         push_back(x)
#define mp(x,y)       make_pair(x,y)
#define MAX           1e18
#define MIN           -1e18
#define MOD           1000000007
#define vectdef(x,size,val) vector<ll> x;for(ll i=0;i<size;i++){x.push_back(val);}
#define vectdef1(x,size,val) vector<ll> x;for(ll i=0;i<=size;i++){x.push_back(val);}
#define INF 10000

using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////
//Utility functions for convex Hull
///////////////////////////////////////////////////////////////////////////////////////////////////

// https://www.codeproject.com/Tips/84226/Is-a-Point-inside-a-Polygon
// This funciton isnt accurate for points on boundary so we will need to check again if point lies
//on boundary of layer or not.
bool pointIsInPoly(pair<ll,ll> p, vector<pair<ll,ll>> poly){ 
    bool isInside = false;   
    ll i = 0, j = (int)poly.size() - 1;
    for (i, j; i < poly.size(); j = i++) {
        if ( (poly[i].second>p.second)!=(poly[j].second>p.second) && p.first<float((poly[j].first-poly[i].first)*(float)(p.second-poly[i].second)/(float)(poly[j].second-poly[i].second)+(float)poly[i].first)) {
             isInside = !isInside;
        }
    }
    return isInside;
}
//This funciton checks for the orientation of a point with respect to a line
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
ll cworccw(pair<ll,ll> a,pair<ll,ll> b,pair<ll,ll> c){
    ll ans = ((b.second - a.second) * (c.first - b.first)) - ((b.first - a.first)*(c.second-b.second));
    if(ans==0){
        return 0; //collinear
    }else{
        if(ans>0){
            return 1; //cw
        }else{
            return 2; //ccw
        }
    }
}
bool cmp(pair<ll,ll> a,pair<ll,ll> b) {
    return a.first < b.first || (a.first == b.first && a.second < b.second);
}
//Same function to check orientation Clockwise
bool cw(pair<ll,ll> a,pair<ll,ll> b,pair<ll,ll> c){
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < 0;
}
//Same function to check orientation Counterclockwise
bool ccw(pair<ll,ll> a,pair<ll,ll> b,pair<ll,ll> c){
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) > 0;
}
//Function to check collinearity 
//I was wondering why this collinear function is giving be WA i was stuck at 80 points due to this one
// bool collinear(pair<ll,ll> a,pair<ll,ll> b,pair<ll,ll> c) {
//     long double distac = sqrtl((a.second-c.second)*(a.second-c.second)+(a.first-c.first)*(a.first-c.first));
//     long double distbc = sqrtl((b.second-c.second)*(b.second-c.second)+(b.first-c.first)*(b.first-c.first));
//     long double distab = sqrtl((a.second-b.second)*(a.second-b.second)+(a.first-b.first)*(a.first-b.first));
//     if(distab == (distbc+distac)){
//         return true;
//     } else return false;
// }
//This one is working fine
bool collinear(pair<ll,ll> a,pair<ll,ll> b,pair<ll,ll> c) {
    if(a.first * (b.second - c.second) +  b.first * (c.second - a.second) +  c.first * (a.second - b.second) == 0){
        return true;
    } else return false;
}
///////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////

//=====================================================================================================
//Taking reference from
//https://cp-algorithms.com/geometry/grahams-scan-convex-hull.html
pair< vector< pair<ll,ll> >,vector< pair<ll,ll> > > convexHull(vector< pair<ll,ll> >  a) {
    vector<pair<ll,ll>> lo;
    vector<pair<ll,ll>> hull;
    for(ll i=0;i<a.size();i++){
        lo.pb(a[i]);
    }
    if (a.size() == 1){
        return mp(lo,hull);
    }
    sort(a.begin(), a.end(), &cmp);
    pair<ll,ll> p1 = a[0], p2 = a.back();
    vector<pair<ll,ll>> up, down;
    up.push_back(p1);
    down.push_back(p1);
    for (int i = 1; i < (int)a.size(); i++) {
        if (i == a.size() - 1 || cw(p1, a[i], p2)) {
            while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i]))
                up.pop_back();
            up.push_back(a[i]);
        }
        if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
            while(down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i]))
                down.pop_back();
            down.push_back(a[i]);
        }
    }
    for (int i = 0; i < (int)up.size(); i++){
        hull.push_back(up[i]);
        lo.erase(remove(lo.begin(), lo.end(), up[i]), lo.end());
    }   
    for (int i = down.size() - 2; i > 0; i--){
        hull.push_back(down[i]);
        lo.erase(remove(lo.begin(), lo.end(), down[i]), lo.end());
    }
    vector < pair<ll,ll> > tmp = lo;
    for(int i=0;i<tmp.size();i++){
        for(ll j = 0;j<hull.size();j++) {
            ll x = cworccw(hull[j],hull[(j + 1) % hull.size()],tmp[i]);
            if(!x){
                lo.erase(remove(lo.begin(),lo.end(), tmp[i]),lo.end());
                //cout<<tmp[i].first<<","<<tmp[i].second<<" "<<"Remove kr diya \n";
            }   
        }
    }
    return mp(lo,hull);
}
//===========================================================================================================



int main(){
    fio;
    cinll(t);
    for(ll i=0;i<t;i++){
        vector<pair<ll,ll>> pts;
        vector<pair<ll,ll>> leftout;  //To keep track of leftout points to be used to construct next concentric hull
        cinll(n);cinll(q);
        for(ll i=0;i<n;i++){
            cinll(x);cinll(y);
            pts.pb(mp(x,y));
            leftout.pb(mp(x,y));
        }
        vector< vector<pair<ll,ll>> > concentrichulls; //2D adj list to store hulls (memoization part)
        ll noofhulls = 0;
        while(leftout.size()>2){                //Creating concentrichulls
            pair< vector<pair<ll,ll>>,vector<pair<ll,ll>> > temphulllo = convexHull(leftout);
            if(temphulllo.second.size()>0){
                concentrichulls.pb(temphulllo.second);
                noofhulls++;
            }
            leftout = temphulllo.first;
        }
        //debug to print convex hulls
        // for(ll i=0;i<noofhulls;i++){
        //     cout<<"{ ";
        //     for(ll j=0;j<concentrichulls[i].size();j++){
        //         cout<<"("<<concentrichulls[i][j].first<<","<<concentrichulls[i][j].second<<")"<<",";
        //     }
        //     cout<<"}\n";
        // }
        //Processing queries
        while(q--){
            cinll(x);cinll(y);
            ll countlayer = 0;
            pair<ll,ll> xy = mp(x,y);
            for(ll i = 0;i<noofhulls;i++){  //traversing each hull
                if(pointIsInPoly(xy,concentrichulls[i])){  //checking weather points lie inside or not
                    bool ckcollinear = false; //side case to check if a point lies on boundary or not
                    for(ll j=0;j<concentrichulls[i].size();j++){
                        if(collinear(concentrichulls[i][j],concentrichulls[i][(j+1)%concentrichulls[i].size()],xy)){
                            ckcollinear = true;
                        }
                    } 
                    bool exiting = false; //if any of hull doesnt contain a candle its concentric ones will not conatin it too. So we can exit from this query
                    if(!ckcollinear){ 
                        countlayer++;
                        exiting = true;
                    }
                    if(exiting==false){
                        goto ext;
                    }
                }else{
                    break;
                }
            }
            ext:;
            cout<<countlayer<<"\n";

        }
    }   
    return 0;
}