Convex Hulk CONHULK Solution

Convex Hulk CONHULK Solution Codechef

by

Convex Hulk CONHULK Solution

Hulk has a set of distinct points P in the 2D plane. His signature move is Hulk Smash. He performed Hulk Smash on the set P which caused the points to change, and so he obtained a new set of points P′.

More formally, Hulk Smash makes the new set P′ in the following way:

  • Initially, let P′ be empty.
  • For every Pi and Pj such that 1≤i<j≤N, add the mid point of Pi and Pj to the set P′ (only if it didn’t exist in it already).

So, P′ is the set of midpoints of line segments connecting pairs of distinct points of P. Note that points from P do not necessarily have to be in P′. See the samples below for a graphical example.

Find the number of points of P′ which lie on the convex hull of P′. A point is said to lie on the convex hull if the shape of the convex hull is changed when this point is removed.

Input Format

  • The first line contains a single integer T, denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer N, denoting the size of P.
  • The next N lines contain two space-separated integers each, where the i-th line contains Pi.x, Pi.y denoting the x-coordinate and y-coordinate of the i-th point.

Output Format

For each test case, print a single line containing one integer the number of points of P′ which lie on its convex hull.

Constraints

  • 1≤T≤20
  • 3≤N≤2⋅105
  • −5⋅108 ≤ Pi.x, Pi.y ≤ 5⋅108
  • The convex hull of the input set P has positive area
  • Sum of N over all tests cases does not exceed 2⋅105

Subtasks

Subtask 1 (20 points):

  • Sum of N over all test cases does not exceed 103

Subtask 2 (80 points):

  • Original constraints

Sample Input 1

2
7
1 7
-6 -5
1 -6
-6 7
-4 3
-2 6
-3 -6
4
1 8
1 4
1 0
5 4

Sample Output 1

8
4

Explanation

  • In the below images, the set of points P is denoted by the color pink, the set of points P′ is denoted by the color green. The blue point is the origin.
  • The below image represents the first test case
  • Convex Hulk CONHULK Solution Codechef
  • The below image represents the second test case
  • Convex Hulk CONHULK Solution Codechef

Note that by our definition, points (1,4) and (3,4) are not considered to lie on the convex hull of P′, because removing one of them does not change the shape of the hull.

SOLUTION

Program Python: Convex Hulk CONHULK Solution in Python

from functools import reduce
import sys
def get_midpoints(pts):
    midpts = []
    n = len(pts)
    for i in range(n):
        for j in range(i+1, n):
            x = (pts[i][0] + pts[j][0]) / 2
            y = (pts[i][1] + pts[j][1]) / 2
            midpts.append((x, y))
    return midpts
def is_left_turn(p, q, r):
    expr = (q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1])
    return expr > 0
def keep_left(hull, r):
    while len(hull) > 1 and not is_left_turn(hull[-2], hull[-1], r):
        hull.pop()
    if not len(hull) or hull[-1] != r:
        hull.append(r)
    return hull
def get_convex_hull(points):
    points = sorted(points)
    l = reduce(keep_left, points, [])
    u = reduce(keep_left, reversed(points), [])
    return l.extend(u[i] for i in range(1, len(u) - 1)) or l
t = int(sys.stdin.readline())
for t_itr in range(t):
    n = int(sys.stdin.readline().strip())
    pts = []
    for n_itr in range(n):
        x, y = map(int, sys.stdin.readline().strip().split())
        pts.append((x, y))
    ans = len(get_convex_hull(get_midpoints(pts)))
    sys.stdout.write(str(ans) + '\n')

Program C++: Convex Hulk CONHULK Solution in C++

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
using LL = long long;
pii operator + (const pii & a, const pii & b) {return pii(a.x + b.x, a.y + b.y);}
pii operator - (const pii & a, const pii & b) {return pii(a.x - b.x, a.y - b.y);}
pii operator * (const pii & a, const int & b) {return pii(a.x * b, a.y * b);}
pii operator / (const pii & a, const int & b) {return pii(a.x / b, a.y / b);}
LL operator * (const pii & a, const pii & b) {return 1ll * a.x * b.x + 1ll * a.y * b.y;}
LL operator ^ (const pii & a, const pii & b) {return 1ll * a.x * b.y - 1ll * a.y * b.x;}
const int NN = 3e5 + 10;
pii p[NN];
int id[NN];
int hull[NN << 1];
int flag[NN];
int rem[NN];
pii temp[NN << 2];
int tp[NN << 2];
int thull[NN << 3];
int tn;
int getHull(pii * p, int * id, int * hull, int n, int cmp) {
	sort(id, id + n, [&](int i, int j) {
		return (p[i].x < p[j].x) || (p[i].x == p[j].x && p[i].y < p[j].y);
	});
	int m = 0;	
	for(int i = 0; i < n; i ++) {
		while(m > 1 && (p[hull[m - 2]] - p[hull[m - 1]] ^ p[id[i]] - p[hull[m - 1]]) > cmp) m --;
		hull[m ++] = id[i];
	}
	for(int i = n - 2, j = m; i >= 0; i --) {
		while(m > j && (p[hull[m - 2]] - p[hull[m - 1]] ^ p[id[i]] - p[hull[m - 1]]) > cmp) m --;
		hull[m ++] = id[i];
	}
	if(m > 1) m --;
	return m;
}
int D(const pii & a) {
	return max(abs(a.x), abs(a.y));
}
int solve() {
	int n; scanf("%d", &n);
	for(int i = 0; i < n; i ++) {
		scanf("%d %d", &p[i].x, &p[i].y);
		p[i] = p[i] * 2;
		id[i] = i;
		flag[i] = 0;
	}
	int m = getHull(p, id, hull, n, 0);
	if(m < 3) {
		return m;
	}
	for(int i = 0; i < m; i ++) {
		flag[hull[i]] = 1;
	}
	int rn = 0;
	for(int i = 0; i < n; i ++) {
		if(flag[i] == 0) {
			rem[rn ++] = i;
		}
	}
	sort(rem, rem + rn, [&] (int i, int j) {
		LL tmp = p[i] - p[hull[0]] ^ p[j] - p[hull[0]];
		if(tmp) return tmp > 0;
		return D(p[i] - p[hull[0]]) < D(p[j] - p[hull[0]]);
	});
	tn = 0;
	for(int i = 0; i < m; i ++) {
		tp[tn] = tn;
		temp[tn ++] = (p[hull[i]] + p[hull[(i + 1) % m]]) / 2;
	}
	for(int i = 0; i < rn; i ++) {
		if((p[hull[m - 1]] - p[hull[1]] ^ p[rem[i]] - p[hull[1]]) > 0) {
			tp[tn] = tn;
			temp[tn ++] = (p[hull[0]] + p[rem[i]]) / 2;
		}
		if((p[hull[0]] - p[hull[2]] ^ p[rem[i]] - p[hull[2]]) > 0) {
			tp[tn] = tn;
			temp[tn ++] = (p[hull[1]] + p[rem[i]]) / 2;
		}
		if((p[hull[m - 2]] - p[hull[0]] ^ p[rem[i]] - p[hull[0]]) > 0) {
			tp[tn] = tn;
			temp[tn ++] = (p[hull[m - 1]] + p[rem[i]]) / 2;
		}
	}
	for(int i = 1, st, ed, md; i <= m - 1; i ++) {
		st = -1, ed = rn;
		while(st + 1 < ed) {
			md = st + ed >> 1;
			if((p[hull[i - 1]] - p[hull[0]] ^ p[rem[md]] - p[hull[0]]) > 0) ed = md;
			else st = md;
		}
		int L = ed;
		st = -1, ed = rn;
		while(st + 1 < ed) {
			md = st + ed >> 1;
			if((p[hull[i + 1]] - p[hull[0]] ^ p[rem[md]] - p[hull[0]]) >= 0) ed = md;
			else st = md;
		}
		int R = ed;
		for(int j = L; j < R; j ++) {
			if((p[rem[j]] - p[hull[i - 1]] ^ p[hull[i + 1]] - p[hull[i - 1]]) > 0) {
				tp[tn] = tn;
				temp[tn ++] = (p[hull[i]] + p[rem[j]]) / 2;
			}
		}
	}
	return getHull(temp, tp, thull, tn, - 1);
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	int T; cin >> T;
	while(T --) {
		printf("%d\n", solve());
	}
	return 0;
}

November Long Challenge 2021 Solution

Leave a Comment

fourteen + 15 =