Header Ads Widget

Simple Polygons | Hackerearth solution

 Problem

Given n simple polygons, no two polygons has common points but one polygon can strictly be inside the other. You are asked to answer q queries of two kinds:

x y: add a point at position (xy).

u: output the number of points inside or on boundary of u-th polygon.

Input Format

The first line of input contains a single integer T, denoting the number of test cases.

Each test case is described as follow: a single line contains an integer n, denoting the number of polygons, each polygon begins with an integer k, denoting the number of vertices, each of k following lines contains two space-seperated integers x y, denoting coordinates of its vertices. The next line contains an integer q, denoting the number of queries. Each queries is described as above.

Output Format

For each query, output a single line contains the answer.

Constraints

  • 1 ≤ T ≤ 5
  • 1 ≤ nq ≤ 105
  • 1 ≤ sum of vertices of all polygons overall test cases ≤ 106
  • 0 ≤ all coordinates ≤ 108
  • 1 ≤ u ≤ n

 

Sample Input
1
4
9
1 1
7 0
10 1
12 6
12 0
14 7
7 8
2 7
1 5
5
3 3
4 4
3 5
4 6
2 6
7
6 1
10 3
8 4
10 6
7 7
6 5
5 4
6
13 1
15 1
16 2
17 1
17 4
15 5
20
1 3 4
2 2
1 5 7
2 2
2 1
1 7 3
2 1
2 2
2 3
1 11 3
1 10 8
1 13 4
2 1
2 2
2 3
1 14 2
2 1
2 2
2 3
2 4

Sample Output
1
1
2
3
1
1
4
1
1
4
1
1
1
Time Limit: 4
Memory Limit: 512
Source Limit:
Explanation

enter image description here

Code(C++):-

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <ctime>
#include <complex>
typedef unsigned long long llu;
typedef long long int lls;
typedef unsigned int uint;
const llu mod = 1000000007;
#define f(i,s,e) for(int i=s;i<e;++i)
#define fe(i,s,e) for(int i=s;i<=e;++i)
 
struct pt {
  pt() {}
  pt(int _x, int _y) : x(_x), y(_y) {};
  int x;
  int y;
};
typedef std::set<int> iset;
typedef std::map<int, int> iimap;
typedef std::vector<int> ivector;
typedef std::vector<char> cvector;
typedef std::pair<int, int> ipair;
typedef std::vector<ipair> ipvector;
typedef std::map<int, ivector> ivimap;
typedef std::pair<pt, pt> segm;
typedef std::vector<segm> svector;
typedef std::vector<pt> ptvector;
typedef std::queue<pt> ptqueue;
 
int N,Q,PN;
 
ptvector *Pl;
ptvector Pt;
ivector  Ppr;
ivector  Pr;
cvector  Bq;
 
enum Etype {
  LINE_BEG = 1,
  ADD_SEGM = 2,
  QR_POINT = 3,
  DEL_SEGM = 4,
  LINE_END = 5,
};
 
struct query {
  int t;
  int x;
  int y;
};
typedef std::vector<query> qvector;
qvector Qr;
 
bool clockw(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (lls)(x2 - x1) * (lls)(y3 - y1) - (lls)(y2 - y1) * (lls)(x3 - x1) < 0;
}
 
struct avltree {
  struct Key {
    int x1;
    int y1;
    int x2;
    int y2;
    int pl;
    bool up;
    bool operator <(const Key& k) const {
      if (x1 == k.x1) {
        if (y1 == k.y1) {
          return (lls)(x2 - k.x1) * (lls)(k.y2 - k.y1) - (lls)(y2 - k.y1) * (lls)(k.x2 - k.x1) > 0;
        }
        if (y1 < k.y1) return true;
        if (y1 > k.y1) return false;
 
        if (y2 < k.y2)return true;
        if (x2 < k.x2)return true;
        if (pl < k.pl)return true;
        if (up < k.up)return true;
        return false;
      }
      if (x1 < k.x1) {
        return (lls)(k.x1 - x1) * (lls)(y2 - y1) - (lls)(k.y1 - y1) * (lls)(x2 - x1) < 0;
      }
      else {
        return (lls)(x1 - k.x1) * (lls)(k.y2 - k.y1) - (lls)(y1 - k.y1) * (lls)(k.x2 - k.x1) > 0;
      }
    }
    bool operator >(const Key& k) const {
      if (*this == k)return false;
      return !(*this < k);
    }
    bool operator ==(const Key& k) const {
      if (x1 != k.x1)return false;
      if (y1 != k.y1)return false;
      if (y2 != k.y2)return false;
      if (x2 != k.x2)return false;
      if (pl != k.pl)return false;
      if (k.up != up)return false;
      return true;
    }
  };
 
  struct Node
  {
    Key key;
    struct Node *left;
    struct Node *right;
    int height;
  };
  typedef std::vector<Node*> npvector;
  avltree() {
    rt = 0;
  }
  void delete_n(struct Node* root) {
    if (root == 0)return;
    Node * np1 = root->left;
    Node * np2 = root->right;
    delete root;
    delete_n(np1);
    delete_n(np2);
  }
  ~avltree() {
    delete_n(rt);
  }
  int height(struct Node *n)
  {
    return (n == NULL) ? 0:n->height;
  }
 
  struct Node* newNode(const Key& key)
  {
    struct Node* node = new Node;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;  
    return(node);
  }
 
  struct Node *rightRotate(struct Node *y)
  {
    struct Node *x = y->left;
    struct Node *T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = std::max(height(y->left), height(y->right)) + 1;
    x->height = std::max(height(x->left), height(x->right)) + 1;
    return x;
  }
  struct Node *leftRotate(struct Node *x)
  {
    struct Node *y = x->right;
    struct Node *T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = std::max(height(x->left), height(x->right)) + 1;
    y->height = std::max(height(y->left), height(y->right)) + 1;
    return y;
  }
  int getBalance(struct Node *n)
  {
    if (n == NULL) return 0;
    return height(n->left) - height(n->right);
  }
  struct Node* insert(struct Node* node, const Key& key)
  {
    if (node == NULL) return(newNode(key));
    if (key < node->key) node->left = insert(node->left, key);
    else node->right = insert(node->right, key);
    node->height = 1 + std::max(height(node->left),height(node->right));
    int balance = getBalance(node);
    if (balance > 1 && key < node->left->key) return rightRotate(node);
    if (balance < -1 && key > node->right->key) return leftRotate(node);
    if (balance > 1 && key > node->left->key)
    {
      node->left = leftRotate(node->left);
      return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key)
    {
      node->right = rightRotate(node->right);
      return leftRotate(node);
    }
    return node;
  }
  struct Node * minValueNode(struct Node* node)
  {
    struct Node* current = node;
    while (current->left != NULL) current = current->left;
    return current;
  }
  struct Node* deleteNode(struct Node* root, const Key& key)
  {
    if (root == NULL)return root;
    if (key == root->key)
    {
      if ((root->left == NULL) || (root->right == NULL))
      {
        struct Node *temp = root->left ? root->left : root->right;
        if (temp == NULL)
        {
          temp = root;
          root = NULL;
        }
        else *root = *temp;
        delete temp;
      }
      else
      {
        struct Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
      }
    } else if (key < root->key) root->left = deleteNode(root->left, key);
    else root->right = deleteNode(root->right, key);
    if (root == NULL) return root;
    root->height = 1 + std::max(height(root->left),height(root->right));
    int balance = getBalance(root);
    if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root);
    if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); }
    if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root);
    if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); }
    return root;
  }
  int compare(Key& k, int x, int y) {
    if (k.x1 == x && k.y1 == y || k.x2 == x && k.y2 == y)return 0;
    lls rs = (lls)(x - k.x1) * (lls)(k.y2 - k.y1) - (lls)(y - k.y1) * (lls)(k.x2 - k.x1);
    if (rs == 0) return 0;
    return (rs < 0) ? -1 : 1;
  }
  int find(Node* root, int x, int y, char msk, Key& k1, Key& k2) {
    if (root == NULL)return (msk==3)? 2:0;
    int kc = compare(root->key, x, y);
    if (kc < 0) {
      k1 = root->key;
      return find(root->right, x, y, msk |= 1, k1, k2);
    }
    else if(kc>0) {
      k2 = root->key;
      return find(root->left, x, y, msk |= 2, k1, k2);
    }
    k1 = root->key;
    return 1;
  }
 
  Node * rt;
};
 
struct event {
  event() {};
  int  x;
  int  pl_idx;
  int  pn_idx;
  int  incr;
  int  y1;
  int  y2;
  avltree::Key key;
  Etype  etype;
  bool operator<(const event& e) const {
    if (x > e.x)return true;
    if (x < e.x)return false;
    if (etype > e.etype)return true;
    return false;
  }
};
typedef std::priority_queue<event> equeue;
equeue E;
 
int nxtpnt(int pli, int pni, int incr) {
  int nxi;
  if (incr >= 0) {
    nxi = pni + 1; if (nxi == (int)Pl[pli].size())nxi = 0;
  }
  else {
    nxi = pni - 1; if (nxi < 0) nxi = (int)Pl[pli].size() - 1;
  }
  return nxi;
}
 
typedef std::map <int, ipair> iipmap;
iipmap SMap;
 
int get_parent_pl(avltree & tr, int x, int y) {
  avltree::Key k1;
  avltree::Key k2;
  int kn = tr.find(tr.rt, x, y, 0, k1, k2);
  if (kn == 0) return -1;
  if (kn == 1) return k1.pl;
  if (k1.pl == k2.pl) {
    if (k1.up == true && k2.up == false) {
      return Pr[k1.pl];
    }
    if (k1.up == false && k2.up == true) {
      return k1.pl;
    }
    exit(1);
    return k1.pl;
   
  }
  if (k1.up == true && k2.up == true) {
    return k2.pl;
  }
  if (k1.up == false && k2.up == false) {
    return k1.pl;
  }
  return Pr[k1.pl];
}
int get_parent(avltree & tr, int x, int y) {
  if (SMap.size() > 0) {
    auto itr = SMap.lower_bound(y);
    if (itr != SMap.end()) {
      if (itr->second.first <= y)return itr->second.second;
    }
  }
  return get_parent_pl(tr, x, y);
}
 
void presolve() {
  Pr.assign(N, -1);
  PN = (int)Pt.size();
  Ppr.assign(PN, -1);
  ivector Dn(N, 0);
  f(i, 0, N) {
    if (Bq[i] == 0)continue;
    f(j, 0, (int)Pl[i].size()) {
      int pj = nxtpnt(i, j, -1);
      int nj = nxtpnt(i, j, 1);
      if (Pl[i][pj].x > Pl[i][j].x) {
        while(Pl[i][nj].x == Pl[i][j].x) nj = nxtpnt(i, nj, 1);
        if (Pl[i][nj].x > Pl[i][j].x) {
          event e;
          e.etype = LINE_BEG;
          e.x = Pl[i][j].x;
          e.pl_idx = i;
          e.pn_idx = j;
          e.incr = 0;
          E.push(e);
        }
      }
      else if (Pl[i][pj].x == Pl[i][j].x) {
        event e;
        e.etype = ADD_SEGM;
        e.x = Pl[i][j].x;
        e.pl_idx = i;
        e.y1 = Pl[i][j].y;
        e.y2 = Pl[i][pj].y;
        e.pn_idx = (e.y1<e.y2)? j:pj;
        E.push(e);
      }
    }
  }
  f(i, 0, PN) {
    event e;
    e.etype = QR_POINT;
    e.x = Pt[i].x;
    e.pl_idx = -1;
    e.pn_idx = i;
    e.incr=0;
    E.push(e);
  }
  avltree tr;
  int lIdx = 1;
  while(!E.empty()) {
    event e = E.top(); E.pop();
    int curx = e.x;
    if (e.etype == ADD_SEGM) {
      int y1 = e.y1;
      int y2 = e.y2;
      if (y1 > y2)std::swap(y1,y2);
      SMap[y2]=std::make_pair(y1,e.pl_idx);
      e.etype = DEL_SEGM;
      E.push(e);
    } else if (e.etype == DEL_SEGM) {
      SMap.erase(std::max(e.y1,e.y2));
    }
    else if (e.etype == LINE_BEG) {
      int pli = e.pl_idx;
      int pni = e.pn_idx;
      int idx = get_parent_pl(tr, Pl[pli][pni].x,Pl[pli][pni].y);
      bool brev = false;
      if (Dn[pli]==0) {  Pr[pli] = idx;  Dn[pli] = 1; }
      if (idx == pli) brev = true;
 
      int nxi = nxtpnt(pli, pni, 1);
      int pxi = nxtpnt(pli, pni, -1);
      int x1 = Pl[pli][pni].x;
      int y1 = Pl[pli][pni].y;
      int x0 = Pl[pli][pxi].x;
      int y0 = Pl[pli][pxi].y;
      int x2 = Pl[pli][nxi].x;
      int y2 = Pl[pli][nxi].y;
      if (clockw(x1, y1, x0, y0, x2, y2)) {
        int y1a = y1;
        while (x0 == x1) {
          y1a = y0;
          pxi = nxtpnt(pli, pxi, -1);
          x0 = Pl[pli][pxi].x;
          y0 = Pl[pli][pxi].y;
        }
        avltree::Key k1;
        k1.pl = pli;
        k1.x1 = x1;
        k1.y1 = y1a;
        k1.x2 = x0;
        k1.y2 = y0;
        k1.up = (brev) ? false : true;
        tr.rt = tr.insert(tr.rt, k1);
        y1a = y1;
        while (x2 == x1) {
          y1a = y2;
          nxi = nxtpnt(pli, nxi, 1);
          x2 = Pl[pli][nxi].x;
          y2 = Pl[pli][nxi].y;
        }
        avltree::Key k2;
        k2.pl = pli;
        k2.x1 = x1;
        k2.y1 = y1a;
        k2.x2 = x2;
        k2.y2 = y2;
        k2.up = (brev) ? true : false;
        tr.rt = tr.insert(tr.rt, k2);
 
        event ev;
        ev.pl_idx = pli;
        ev.etype = LINE_END;
        ev.key = k1;
        ev.pn_idx = pxi;
        ev.incr = -1;
        ev.x = x0;
        E.push(ev);
        ev.key = k2;
        ev.pn_idx = nxi;
        ev.incr = 1;
        ev.x = x2;
        E.push(ev);
      }
      else {
        int y1a = y1;
        while (x0 == x1) {
          y1a = y0;
          pxi = nxtpnt(pli, pxi, -1);
          x0 = Pl[pli][pxi].x;
          y0 = Pl[pli][pxi].y;
        }
        avltree::Key k1;
        k1.pl = pli;
        k1.x1 = x1;
        k1.y1 = y1a;
        k1.x2 = x0;
        k1.y2 = y0;
        k1.up = (brev) ? true : false;
        tr.rt = tr.insert(tr.rt, k1);
 
        y1a = y1;
        while (x2 == x1) {
          y1a = y2;
          nxi = nxtpnt(pli, nxi, 1);
          x2 = Pl[pli][nxi].x;
          y2 = Pl[pli][nxi].y;
        }
        avltree::Key k2;
        k2.pl = pli;
        k2.x1 = x1;
        k2.y1 = y1a;
        k2.x2 = x2;
        k2.y2 = y2;
        k2.up = (brev) ? false : true;
        tr.rt = tr.insert(tr.rt, k2);
 
        event ev;
        ev.pl_idx = pli;
        ev.etype = LINE_END;
        ev.key = k1;
        ev.pn_idx = pxi;
        ev.incr = -1;
        ev.x = x0;
        E.push(ev);
        ev.key = k2;
        ev.pn_idx = nxi;
        ev.incr = 1;
        ev.x = x2;
        E.push(ev);
      }
    }
    else if (e.etype == QR_POINT) {
      int idx = get_parent(tr, Pt[e.pn_idx].x, Pt[e.pn_idx].y);
      Ppr[e.pn_idx] = idx;
    }
    else if (e.etype == LINE_END) {
      avltree::Key key = e.key;
      int pli = e.pl_idx;
      int pni = e.pn_idx;
      tr.rt = tr.deleteNode(tr.rt, key);
      int nxi = nxtpnt(pli, pni, e.incr);
      int x1 = Pl[pli][pni].x;
      int y1 = Pl[pli][pni].y;
      int x2 = Pl[pli][nxi].x;
      int y2 = Pl[pli][nxi].y;
      while (x2 == x1) {
        pni = nxi; x1 = x2; y1 = y2;
        nxi = nxtpnt(pli, pni, e.incr);
        x2 = Pl[pli][nxi].x;
        y2 = Pl[pli][nxi].y;
      }
      if (x2 > x1) {
        key.x1 = x1;
        key.y1 = y1;
        key.x2 = x2;
        key.y2 = y2;
        tr.rt = tr.insert(tr.rt, key);
        event ev;
        ev.pl_idx = pli;
        ev.etype = LINE_END;
        ev.key = key;
        ev.pn_idx = nxi;
        ev.incr = e.incr;
        ev.x = x2;
        E.push(ev);
      }
    }
  }
}
 
void solve() {
  ivector Cn(N, 0);
  int ptidx = 0;
  f(i, 0, Q) {
    if (Qr[i].t == 1) {
      int pr = Ppr[ptidx];
      while (pr >= 0) {
        Cn[pr]+=1;
        pr = Pr[pr];
      }
      ++ptidx;
    }
    else {
      printf("%d\n", Cn[Qr[i].x-1]);
    }
  }
}
 
 
int main(int argc, char **argv){
  clock_t start_tm = clock();
  int T;
  scanf("%d", &T);
  Pl = new ptvector[100000];
  f(t, 0, T) {
    scanf("%d", &N);
    f(i, 0, N) {
      int n;
      scanf("%d", &n);
      Pl[i].clear();
      Pl[i].resize(n);
      f(j, 0, n) scanf("%d %d", &Pl[i][j].x, &Pl[i][j].y);
    }
    scanf("%d", &Q);
    Pt.clear();
    Qr.clear();
    Pt.reserve(Q);
    Qr.resize(Q);
    Bq.assign(N, 0);
    f(i, 0, Q) {
      scanf("%d", &Qr[i].t);
      if (Qr[i].t == 1) {
        scanf("%d %d", &Qr[i].x, &Qr[i].y);
        Pt.push_back(pt(Qr[i].x, Qr[i].y));
      }
      else {
        scanf("%d", &Qr[i].x);
        Qr[i].y = 0;
        Bq[Qr[i].x - 1] = 1;
      }
    }
    presolve();
    solve();}
  fprintf(stderr, "Time: %lf\n", (double)(clock() - start_tm) / (double)CLOCKS_PER_SEC);
  return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-