কনভেক্স হাল(Convex Hull)

If you don't know what Convex Hull is,read the following articles sequentially.Hope,you'll get vast knowledge.Since there are a lot of tutorials on Convex Hull,we'll rather discuss here some related problems & their solutions.

Tutorials on Convex Hull & it's prerequisites:

1.Orientation of 3 ordered points(prerequisite)
2.How to check if two given line segments intersect?(prerequisite)
3.Implementation of Graham Scan Algorithm for Convex Hull(Implementation)

Sample source Code:

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define mx 100000+10
	#define PI 3.14159265358979323846
	struct Point{
	ll x,y;
	}P[mx],ans[mx];
	Point Pivot;
	ll orientation(Point p,Point q,Point r){
	return ((q.y-p.y)*(r.x-q.x))-((r.y-q.y)*(q.x-p.x));
	}
	ll dist(Point p1,Point p2){
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
	}
	bool cmp(Point a,Point b){
	if(orientation(Pivot,a,b)==0) //checking co-linearity
	return dist(Pivot,a)<dist(Pivot,b); //if co-linear put nearest one
	ll slop1x=a.x-Pivot.x; ll slop1y=a.y-Pivot.y;
	ll slop2x=b.x-Pivot.x; ll slop2y=b.y-Pivot.y;
	return (atan2((double)slop1y,(double)slop1x)-atan2((double)slop2y,(double)slop2x))<0;
	}
	Point nextToTop(stack<Point> &S)
	{
	Point p = S.top();
	S.pop();
	Point res = S.top();
	S.push(p);
	return res;
	}
	void ConvexHull(ll N){
	ll ymin=P[0].y,mn=0;
	for(int i=1;i<N;i++){ //Finding the bottom-most point
	if(P[i].y<ymin || (ymin==P[i].y && P[i].x<P[mn].x)){
	ymin=P[i].y; mn=i;
	}
	}
	swap(P[0],P[mn]); //place the bottom-most point in the 1st position
	Pivot=P[0];
	sort(&P[1],P+N,cmp);
	ll m=1;
	for(int i=1;i<N;i++){
	while(i<N-1 && orientation(Pivot,P[i],P[i+1])==0) i++; //removing same angle points
	P[m++]=P[i];
	}
	cout<<m<<endl;
	if(m<3) return; //Convex Hull is not possible
	stack<Point> S;
	S.push(P[0]);
	S.push(P[1]);
	S.push(P[2]);
	for(int i=3;i<m;i++){
	while (orientation(nextToTop(S),S.top(),P[i])>=0) //clockwise
	S.pop();
	S.push(P[i]);
	}
	while(!S.empty()){
	Point p=S.top();
	cout<<p.x<<' '<<p.y<<endl;
	S.pop();
	}
	}
	int main()
	{
	ll N,a,b;
	scanf("%lld",&N);
	for(int i=0;i<N;i++){
	scanf("%lld%lld",&P[i].x,&P[i].y);
	}
	cout<<endl;
	ConvexHull(N);
	return 0;
	}

view raw Convex Hull.cpp hosted with ❤ by GitHub

Related Problems & Solutions:

1. LightOj 1203 - Guarding Bananas

          Solution Idea: Straightforward

          i) Make Convex Hull of the given points.

          ii) Find angle for each point with respect to it's adjacent line segment.

          iii) Answer the minimum of them(angles).

          iv) If a,b,c are line segments & ∆abc is a triangle,the angle between a & c is acos((a*a+c*c-b*b)/2*a*c)) in radian.

          v) degree=radian*(180/𝞹).

Solution:

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define mx 100000+10
	#define PI 3.14159265358979323846
	struct Point{
	ll x,y;
	}P[mx],ans[mx];
	Point Pivot;
	ll orientation(Point p,Point q,Point r){
	return ((q.y-p.y)*(r.x-q.x))-((r.y-q.y)*(q.x-p.x));
	}
	ll dist(Point p1,Point p2){
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
	}
	double calc(Point A,Point B,Point C)
	{
	double a = sqrt((double)dist(A,B));
	double b = sqrt((double)dist(B,C));
	double c = sqrt((double)dist(C,A));
	return acos((a*a+c*c-b*b)/(2*a*c)); //Trigonometric formula of finding angle in a triangle in radian
	}
	bool cmp(Point a,Point b){
	if(orientation(Pivot,a,b)==0) //checking co-linearity
	return dist(Pivot,a)<dist(Pivot,b); //if co-linear put nearest one
	ll slop1x=a.x-Pivot.x; ll slop1y=a.y-Pivot.y;
	ll slop2x=b.x-Pivot.x; ll slop2y=b.y-Pivot.y;
	return (atan2((double)slop1y,(double)slop1x)-atan2((double)slop2y,(double)slop2x))<0; //sorting in descending order of slop
	}
	Point nextToTop(stack<Point> &S)
	{
	Point p = S.top();
	S.pop();
	Point res = S.top();
	S.push(p);
	return res;
	}
	double ConvexHull(ll N){
	ll ymin=P[0].y,mn=0;
	for(int i=1;i<N;i++){ //Finding the bottom-most point
	if(P[i].y<ymin || (ymin==P[i].y && P[i].x<P[mn].x)){
	ymin=P[i].y; mn=i;
	}
	}
	swap(P[0],P[mn]); //place the bottom-most point in the 1st position
	Pivot=P[0];
	sort(&P[1],P+N,cmp);
	ll m=1;
	for(int i=1;i<N;i++){
	while(i<N-1 && orientation(Pivot,P[i],P[i+1])==0) i++; //removing same angle points
	P[m++]=P[i];
	}
	if(m<3) return 0.0; //Convex Hull is not possible
	stack<Point> S;
	S.push(P[0]);
	S.push(P[1]);
	S.push(P[2]);
	for(int i=3;i<m;i++){
	while (orientation(nextToTop(S),S.top(),P[i])>=0) //clockwise or right turn..so ignore it
	S.pop();
	S.push(P[i]);
	}
	int cnt=0;
	while(!S.empty()){
	Point p=S.top();
	ans[cnt++]=p;
	S.pop();
	}
	vector<Point>V;
	for(int i=cnt-1;i>=0;i--)V.push_back(ans[i]);
	int sz=V.size();
	double ret=180.0;
	for(int i=0;i<V.size();i++){ //angle of each point w.r.t it's adjacent points
	int j=(i+1)%sz;
	int k=(i-1+sz)%sz;
	ret = min(ret,(calc(V[i],V[j],V[k])*180)/PI); //degree=radian*(180/PI)
	}
	return ret;
	}
	int main()
	{
	ll N,a,b,tc,cs=0;
	scanf("%lld",&tc);
	while(tc--){
	scanf("%lld",&N);
	for(int i=0;i<N;i++){
	scanf("%lld%lld",&P[i].x,&P[i].y);
	}
	printf("Case %lld: %0.6f\n",++cs,ConvexHull(N));
	}
	return 0;
	}

view raw LightOj 1203.cpp hosted with ❤ by GitHub

2. LightOj 1239 - Convex Fence
          Solution Idea: Straightforward
          i) Make Convex Hull of the given points.
          ii) Find it's perimeter.
          But this is not the actual answer,we've to add 2*𝞹*d to it.why?Because the problem indicates that the minimum distance of any tree to fence at least d units.
          if we think of n=1,we can assume it as circle of radius d.So,the answer will be mere 2*𝞹*d(perimeter of the circle).
          if we think of n=2, we can imagine the following picture(collected)

if we think of n>2,we can imagine the following pictures(collected)

From the above pictures,it is clear that joining several same circles make 360°.So the solution is simple,add 2*𝞹*d to the perimeter of the Convex Hull(n>2).

Solution:

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define mx 100000+10
	#define PI 3.14159265358979323846
	struct Point{
	ll x,y;
	}P[mx],ans[mx];
	Point Pivot;
	ll orientation(Point p,Point q,Point r){
	return ((q.y-p.y)*(r.x-q.x))-((r.y-q.y)*(q.x-p.x));
	}
	ll dist(Point p1,Point p2){
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
	}
	bool cmp(Point a,Point b){
	if(orientation(Pivot,a,b)==0) //checking co-linearity
	return dist(Pivot,a)<dist(Pivot,b); //if co-linear put nearest one
	ll slop1x=a.x-Pivot.x; ll slop1y=a.y-Pivot.y;
	ll slop2x=b.x-Pivot.x; ll slop2y=b.y-Pivot.y;
	return (atan2((double)slop1y,(double)slop1x)-atan2((double)slop2y,(double)slop2x))<0;
	}
	Point nextToTop(stack<Point> &S)
	{
	Point p = S.top();
	S.pop();
	Point res = S.top();
	S.push(p);
	return res;
	}
	double ConvexHull(ll N){
	ll ymin=P[0].y,mn=0;
	for(int i=1;i<N;i++){ //Finding the bottom-most point
	if(P[i].y<ymin || (ymin==P[i].y && P[i].x<P[mn].x)){
	ymin=P[i].y; mn=i;
	}
	}
	swap(P[0],P[mn]); //place the bottom-most point in the 1st position
	Pivot=P[0];
	sort(&P[1],P+N,cmp);
	ll m=1;
	for(int i=1;i<N;i++){
	while(i<N-1 && orientation(Pivot,P[i],P[i+1])==0) i++; //removing same angle points
	P[m++]=P[i];
	}
	//if(m<3) return; //Convex Hull is not possible
	stack<Point> S;
	S.push(P[0]);
	S.push(P[1]);
	S.push(P[2]);
	for(int i=3;i<m;i++){
	while (orientation(nextToTop(S),S.top(),P[i])>=0) //clockwise
	S.pop();
	S.push(P[i]);
	}
	int cnt=0;
	while(!S.empty()){
	Point p=S.top();
	ans[cnt++]=p;
	S.pop();
	}
	vector<Point>V;
	for(int i=cnt-1;i>=0;i--)V.push_back(ans[i]);
	int sz=V.size();
	double perim=0.0;
	V[sz]=V[0];
	for(int i=0;i<sz;i++){
	perim+=sqrt(dist(V[i],V[i+1]));
	}
	return perim;
	}
	int main()
	{
	ll N,a,b,tc,cs=0;
	double d;
	scanf("%lld",&tc);
	while(tc--){
	scanf("%lld%lf",&N,&d);
	for(int i=0;i<N;i++){
	scanf("%lld%lld",&P[i].x,&P[i].y);
	}
	if(N<3){
	double h=2.0*sqrt(dist(P[0],P[1]));
	printf("Case %lld: %0.8f\n",++cs,((double)2.0*PI*d)+h);
	}
	else
	printf("Case %lld: %0.8f\n",++cs,ConvexHull(N)+((double)2.0*PI*d));
	}
	return 0;
	}

view raw LightOj 1239 - Convex Fence.cpp hosted with ❤ by GitHub

3. SPOJ BSHEEP - Build the Fence
          Solution Idea: Straightforward
          i) Make Convex Hull of the given points.
          ii) Find it's perimeter & print.
          iii) Print the indexes by which the Convex Hull is formed.

Solution:

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define mx 100000+10
	#define PI 3.14159265358979323846
	struct Point{
	ll x,y,idx;
	}P[mx],ans[mx];
	Point Pivot;
	ll orientation(Point p,Point q,Point r){
	return ((q.y-p.y)*(r.x-q.x))-((r.y-q.y)*(q.x-p.x));
	}
	ll dist(Point p1,Point p2){
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
	}
	bool cmp(Point a,Point b){
	if(orientation(Pivot,a,b)==0) //checking co-linearity
	return dist(Pivot,a)<dist(Pivot,b); //if co-linear put nearest one
	ll slop1x=a.x-Pivot.x; ll slop1y=a.y-Pivot.y;
	ll slop2x=b.x-Pivot.x; ll slop2y=b.y-Pivot.y;
	return (atan2((double)slop1y,(double)slop1x)-atan2((double)slop2y,(double)slop2x))<0;
	}
	Point nextToTop(stack<Point> &S)
	{
	Point p = S.top();
	S.pop();
	Point res = S.top();
	S.push(p);
	return res;
	}
	void ConvexHull(ll N){
	ll ymin=P[0].y,mn=0;
	for(int i=1;i<N;i++){ //Finding the bottom-most point
	if(P[i].y<ymin || (ymin==P[i].y && P[i].x<P[mn].x)){
	ymin=P[i].y; mn=i;
	}
	}
	swap(P[0],P[mn]); //place the bottom-most point in the 1st position
	Pivot=P[0];
	sort(&P[1],P+N,cmp);
	ll m=1;
	for(int i=1;i<N;i++){
	while(i<N-1 && orientation(Pivot,P[i],P[i+1])==0) i++; //removing same angle points
	P[m++]=P[i];
	}
	if(m==1){
	printf("0.00\n");
	printf("1\n");
	}
	else if(m==2){
	printf("%0.2f\n",2.0*(double)sqrt(dist(P[0],P[1])));
	printf("%lld %lld\n",P[0].idx,P[1].idx);
	}
	else{
	stack<Point> S;
	S.push(P[0]);
	S.push(P[1]);
	S.push(P[2]);
	for(int i=3;i<m;i++){
	while (orientation(nextToTop(S),S.top(),P[i])>=0) //clockwise
	S.pop();
	S.push(P[i]);
	}
	int cnt=0;
	while(!S.empty()){
	Point p=S.top();
	ans[cnt++]=p;
	S.pop();
	}
	vector<Point>V;
	for(int i=cnt-1;i>=0;i--)V.push_back(ans[i]);
	int sz=V.size();
	double perim=0.0;
	for(int i=0;i<sz-1;i++){
	perim+=sqrt(dist(V[i],V[i+1]));
	}
	perim+=sqrt(dist(V[sz-1],V[0]));
	printf("%0.2f\n",perim);
	for(int i=0;i<sz;i++){
	if(i==sz-1)printf("%lld\n",V[i].idx);
	else printf("%lld ",V[i].idx);
	}
	}
	}
	int main()
	{
	ll N,a,b,tc;
	scanf("%lld",&tc);
	while(tc--){
	scanf("%lld",&N);
	for(int i=0;i<N;i++){
	scanf("%lld%lld",&P[i].x,&P[i].y);
	P[i].idx=i+1;
	}
	cout<<endl;
	ConvexHull(N);
	}
	return 0;
	}

view raw SPOJ BSHEEP - Build the Fence.cpp hosted with ❤ by GitHub

4.