# 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

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,
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.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;
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;
}