Convex Hulk CONHULK Solution

Convex Hulk CONHULK Solution Codechef

by

Convex Hulk CONHULK Solution

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

More formally, HulkHulk SmashSmash makes the new set P′P′ in the following way:

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

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

Find the number of points of P′P′ which lie on the convex hull of P′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 TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN, denoting the size of PP.
  • The next NN lines contain two space-separated integers each, where the ii-th line contains Pi.x,Pi.yPi.x,Pi.y denoting the x-coordinate and y-coordinate of the ii-th point.

Output Format

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

Constraints

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

Subtasks

Subtask 1 (20 points):

  • Sum of NN over all test cases does not exceed 103103

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 PP is denoted by the color pink, the set of points P′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)(1,4) and (3,4)(3,4) are not considered to lie on the convex hull of P′P′, because removing one of them does not change the shape of the hull.

Convex Hulk CONHULK Solution is updated. Click Below

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

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September Long Challenge 2021 Solution

Leave a Comment

sixteen − seven =