Page Contents
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
- The below image represents the second test case
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
- Which Fuel is Cheaper CHEAPFUEL Solution
- Convex Hulk CONHULK Solution
- Functional Array FUNARR Solution
- Flip or Compress FLIPCOMP Solution
- Maximise the bridges MAXBRIDGE Solution
- Wildcard Replacement WLDRPL Solution
- Xor Equation XOREQN Solution
- Hill Sequence HILLSEQ Solution
- Weird Palindrome Making MAKEPAL Solution
- Equal Coins EQUALCOIN Solution Codechef
Codechef Long Challenges Solution
October Long Challenge 2021 Solution
- Longest AND Subarray
- MEX-OR
- Digit Removal
- Yet another MEX problem
- Characteristic Polynomial Verification
- Chef at the Olympics
- Which Mixture
- Three Boxes
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield