PROBLEM LINK:
Author: Shubham Jain
Tester: Shubham Jain
Editorialist: Shubham Jain
DIFFICULTY:
Hard
PREREQUISITES:
Convex-hull
PROBLEM:
Welcome to the animal kingdom. We have a friend namely Quirk, a spider. He is fond of building spiral webs in anticlockwise direction throughout the diverse sphere. But he faces a lot of problem to select points in the surroundings. Since the web is 2D, we can consider the points to have 2D points. Help him by specifying the sequence of points to start and end the net. There may arise some ambiguity for choosing the starting point of the web. So for resolution, you need to choose the starting point as the topmost point among the set. Note, the threads don’t intersect at any point.
EXPLANATION:
From the question we can take following observations :
- Given are set of points
- Starting point for the web is point having the “y” coordinate value as the highest
- We will make threads of the web by connecting the points
- First we need to make web by stitching the points in the outer layer in anticlockwise direction
- We never need the processed points again for getting the remaining part of solution
- To get the remaining set of points, we can repeat process specified above in point-4
- Finally, if we don’t have any set of points left, we are now left with the solution in proper order
Solutions to each observation
-
We need to write proper code to take the given input to array.
-
Find the point having the maximum “y” coordinate value using a loop.
-
As a solution, we can keep track of the solution as sequence of points.
-
To get the points on the outer layer, we can use any algorithm for finding set of points of a convex hull. After finding the set of outer points, try to satisfy the requirements of the problem, i.e. anticlockwise direction.
-
Since we never need the points that are already part of the solution, we can remove them from our input data set that will be further processed.
-
We can keep on repeating the convex hull procedure to get another set of points to append in the solution.
-
We can stop repeating the above steps once we have no set of input points remaining.
AUTHOR’s SOLUTION:
#include "iostream"
#include "stack"
#include "stdlib.h"
#include "vector"
#include "climits"
using namespace std;
struct Point{
int x, y;
};
Point p0;
Point nextToTop(stack < Point > &S){
Point p = S.top();
S.pop();
Point res = S.top();
S.push(p);
return res;
}
int swap(Point &p1, Point &p2){
Point temp = p1;
p1 = p2;
p2 = temp;
}
int distSq(Point p1, Point p2){
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
int orientation(Point p, Point q, Point r){
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0)? 1: 2;
}
int compare(const void * vp1, const void * vp2){
Point * p1 = (Point * )vp1;
Point * p2 = (Point * )vp2;
int o = orientation(p0, * p1, * p2);
if (o == 0)
return (distSq(p0, * p2) >= distSq(p0, * p1))? -1 : 1;
return (o == 2)? -1: 1;
}
vector< Point > convexHull(vector< Point > points, int n){
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++){
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
swap(points[0], points[min]);
p0 = points[0];
qsort(&points[ 1 ], n-1, sizeof(Point), compare);
int m = 1;
for(int i = 1; i < n; i++){
while(i < n-1 && orientation(p0, points[i], points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
}
if (m < 3) return points;
stack< Point > S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for(int i = 3; i < m; i++){
while (orientation(nextToTop(S), S.top(), points[i]) != 2)
S.pop();
S.push(points[i]);
}
vector< Point > result;
while (!S.empty()){
Point p = S.top();
result.push_back( p );
S.pop();
}
return result;
}
void display(vector< Point > v){
int start = 0;
int maxY = INT_MIN;
for(int i = 0; i < v.size(); i++){
if(maxY < v[i].y){
maxY = v[i].y;
start = i;
}
}
for(int i = 0; i < v.size(); i++){
int in = start - i;
if(in < 0)
in += v.size();
cout << v[in].x << " " << v[in].y << " ";
}
}
void setDifference(vector< Point > &pts, vector< Point > &result){
vector< Point > tmp(pts.begin(), pts.end());
pts.clear();
pts.resize(0);
for(vector< Point >::iterator a = tmp.begin(); a != tmp.end(); a++){
bool flag = false;
for(vector< Point >::iterator it = result.begin(); it != result.end(); it++){
if(a->x == it->x && a->y == it->y){
flag = true;
}
}
if( ! flag ) {
pts.push_back( * a );
}
}
}
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector< Point > pts(n);
for (int i = 0; i < n; i++)
cin >> pts[i].x >> pts[i].y;
while (n) {
vector< Point > result = convexHull(pts, n);
display(result);
setDifference(pts, result);
n = pts.size();
}
cout << endl;
}
return 0;
}