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:

1 x y: add a point at position (x, y).

2 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 ≤ n, q ≤ 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

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:-

• Count Even Sum
  
• Length of Hypotenuse
  

Capgemini Coding Questions:-

• Move Hash
  
• Character with their frequency
  

iMocha coding Questions:-

• Mathematical Calculation: Prime number
  
• Mathematical calculation : odd numbers
  

Tech Mahindra coding questions:-

• Find Even odd difference
  
• Find Total curtains
  
• Find odd even difference
  
• Find total sum
  

Unthinkable Solutions coding questions:-

• Swap the adjacent characters of the string
  
• Double the vowel characters in the string
  
• Character with their frequency
  
• Program to find the closest value
  

Must check this:-

• PPS lab all the problems of 1st year 
• C- program of CPU scheduling Algorithms

Companies interview:-

• Swap adjacent characters 
• Double the vowel characters
  
• Check valid parenthesis
  
• Print the characters with their frequencies
  
• Find closest value
  
• Word Count
•  Program of CaesarCipher
• Program to find the perfect city
• Annual Day | Tech Mahindra coding question
• Find the number of pairs in the array whose sum is equal to a given target.

Full C course:-    

• C -Tutorial
  

Key points:-

• How to set limit in the floating value in python
  
• What is boolean data type
• How to print any character without using format specifier
• How to check that given number is power of 2 or not
  
• How to fix limit in double and floating numbers after dot (.) in c++
  
• How to print a double or floating point number in scientific notation and fixed notation
  
• How to take input a string in c
  
• How to reduce the execution time of program in c++.
  

Cracking the coding interview:-

 Array and string:-

• Is Unique
  
• Check Permutation
  
• Urlify
  
• One away
  
• String Compression
  
• Zero matrix
  

Tree and graph:-

• Route between nodes
  
• Minimal Tree
  
• List of Depth
  
• Validate BST
  
• Successor
  

Hackerearth Problems:-

• Very Cool numbers | Hacker earth solution
• Vowel Recognition | Hackerearth practice problem solution
  
• Birthday party | Hacker earth solution
• Most frequent | hacker earth problem solution
• program to find symetric difference of two sets
•  cost of balloons | Hacker earth problem solution
• Chacha o chacha | hacker earth problem solution
• jadu and dna | hacker earth solution
• Bricks game | hacker earth problem
• Anti-Palindrome strings | hacker earth solution
• connected components in the graph | hacker earth data structure
• odd one out || hacker earth problem solution
• Minimum addition | Hackerearth Practice problem
  
• The magical mountain | Hackerearth Practice problem
  
• The first overtake | Hackerearth Practice problem
  

Hackerrank Problems:-

•  Playing With Characters | Hackerrank practice problem solution
• Sum and Difference of Two Numbers | hackerrank practice problem solution
  
• Functions in C | hackerrank practice problem solution
  
• Pointers in C | hackerrank practice problem solution
  
• Conditional Statements in C | Hackerrank practice problem solution
  
• For Loop in C | hackerrank practice problem solution
  
• Sum of Digits of a Five Digit Number | hackerrank practice problem solution
  
• 1D Arrays in C | hackerrank practice problem solution
  
• Array Reversal | hackerrank practice problem solution
  
• Printing Tokens | hackerrank practice problem solution
  
• Digit Frequency | hackerrank practice problem solution
  
• Calculate the Nth term | hackerrank practice problem solution

Data structure:-

•   Program to find cycle in the graph
• Implementation of singly link list
• Implementation of queue by using link list
• Algorithm of quick sort
• stack by using link list
• program to find preorder post order and inorder of the binary search tree
• Minimum weight of spanning tree
  
• Preorder, inorder and post order traversal of the tree

Must check this:-

• PPS lab all the problems of 1st year 
• C- program of CPU scheduling Algorithms

 MCQs:-

• Engineering mathematics -4 MCQs
• CSS (Computer cyber security ) MCQS