Convex Hull
In this question our task was to find a polygon which wraps all the points such that all other polygons which wrap these points are bigger than the polygon which we just found out.
Approach:
To get intuition about the problem, at first I read the overleaf notes of the topic Convex hull to get some idea about the problem and how to solve it , then I referred about the same on internet and came to know about two Algorithms, Jarvis March and Graham Scan.
Since Jarvis March method was based on brute force search for angles, it would make the time complexity of our code O(n^2).
So I decided to go with Graham Scan through which I can solve the problem in O(nlogn) time.
Implementation:
1st step: I calculated the angle of my minimum point (left-most) with every other point and stored it in a vector, it took O(n) time.
2nd step: I then sorted the points according to angles, which took O(nlogn) time.
3rd step: I iterated through the vector of points and used the formula of parallelogram’s area calculation to find out if the next point is making a clockwise or an anticlockwise turn.
Formula: (bx-ax) (cy-ay) – (cx-bx) (by-ay)
If the formula gave positive answer then the angle was clockwise ,anticlockwise when negative and zero when collinear.
Clockwise: pass
Anticlockwise: remove 2 top elements and do it for other element by skipping the older element
Collinear: remove the older element
This took -> O(n) time
So Overall time Complexity of the Algorithm : O(nlogn)
Convex Hull In this question our task was to find a polygon which wraps all the points such that all other polygons which wrap these points are bigger than the polygon which we just found out. Approach: To get intuition about the problem, at first I read the overleaf notes of the topic Convex hull to get some idea about the problem and how to solve it , then I referred about the same on internet and came to know about two Algorithms, Jarvis March and Graham Scan. Since Jarvis March method was based on brute force search for angles, it would make the time complexity of our code O(n^2). So I decided to go with Graham Scan through which I can solve the problem in O(nlogn) time. Implementation: 1st step: I calculated the angle of my minimum point (left-most) with every other point and stored it in a vector, it took O(n) time. 2nd step: I then sorted the points according to angles, which took O(nlogn) time. 3rd step: I iterated through the vector of points and used the formula of parallelogram’s area calculation to find out if the next point is making a clockwise or an anticlockwise turn. Formula: (bx-ax) (cy-ay) – (cx-bx) (by-ay) If the formula gave positive answer then the angle was clockwise ,anticlockwise when negative and zero when collinear. Clockwise: pass Anticlockwise: remove 2 top elements and do it for other element by skipping the older element Collinear: remove the older element This took -> O(n) time So Overall time Complexity of the Algorithm : O(nlogn)
hacktoberfest2023