681 - Convex Hull Finding

[Ndiyaa ndako]

While sorting using the Graham algorithm, do not forget to place the lowest point FIRST in the list.

[898989]

I got many wa.
can any one give me test cases

[Darko]

Ok, that's just spamming... please stop doing that.

[ranban282]

I've used Graham's scan, without any floating point arithmetic, and i get wrong answer. Can anyone point out the mistake in my code or give me any test cases?

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
using namespace std;

bool cmp(pair<int,int> p1,pair<int,int> p2)
{
	int temp=p1.second*p2.first-p1.first*p2.second;
	if(temp==0.0)
		return p1.second<p2.second;
	else
		return (temp<=0.0);
	/*else if(temp>0.0)
		return 0;
	else
		return 1;*/
}

bool cmp1(pair<int,int>v1 ,pair<int,int> v2)
{
	if(v2.second==v1.second)
		return v1.first<v2.first;
	else
		return v1.second<v2.second;
}

pair<int,int> next_to_top(vector<pair<int,int> > s)
{
	pair<int,int> p1(0,0);
	if(s.size()>=2)
	{
		vector<pair<int,int> >::iterator i=s.end()-2;
		p1=*i;
	}
	return p1;
}

bool nonleftturn(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3)
{
	pair<int,int> v1(p3.first-p1.first,p3.second-p1.second),v2(p2.first-p1.first,p2.second-p1.second);
	return ((v1.first*v2.second-v1.second*v2.first)>=0);
	
}

vector<pair<int,int> > convexhull(vector<pair<int,int> > v,int n)
{
	vector<pair<int,int> > vertex(n);
	pair<int,int> shift=*(min_element(v.begin(),v.end(),cmp1));
	for(int i=0;i<n;i++)
	{  
		vertex[i].first=v[i].first-shift.first;
		vertex[i].second=v[i].second-shift.second;
	}
	
/*	for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first<<" "<<vertex[i].second<<endl;
	}*/
	sort(vertex.begin(),vertex.end(),cmp);
	/*for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first+shift.first<<" "<<vertex[i].second+shift.second<<endl;
	}*/
		
	vector<pair<int,int> > s;
	s.push_back(vertex[0]);
	s.push_back(vertex[1]);
	s.push_back(vertex[2]);
	for(int i=3;i<n;i++)
	{
		while (s.size()>=2 && nonleftturn(next_to_top(s),s.back(),vertex[i]))
		{
			s.pop_back();
		}
		s.push_back(vertex[i]);
	}	
	for(vector<pair<int,int> >::iterator i=s.begin();i!=s.end();i++)
	{
		(*i).first+=shift.first;
		(*i).second+=shift.second;
	}
	return s;	
}




int main()
{
	int m;
	cin>>m;
	cout<<m<<endl;
	while(m--)
	{

		int n;
		cin>>n;
		vector<pair<int,int> > kingdom(n-1);
		for(int i=0;i<n-1;i++)
		{
			cin>>kingdom[i].first;
			cin>>kingdom[i].second;
		}
		int waste1,waste2,delim;
		cin>>waste1>>waste2;
		if(m!=0)
			cin>>delim;

		vector<pair<int,int> > v=convexhull(kingdom,n-1);
		cout<<v.size()+1<<endl;
		for(int i=0;i<v.size();i++)
		{
			cout<<v[i].first<<" "<<v[i].second<<endl;
		}
		cout<<v[0].first<<" "<<v[0].second<<endl;
		if(m!=0)
			cout<<delim<<endl;

	}	
	return 0;
}

Is there any way I can find out for which test case is my program failing?

[ranban282]

After repeated tries I get WA.
I have used Graham's scan.
Can anyone point the bug in my code or give me test cases??
Here's the code:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
using namespace std;

bool cmp(pair<int,int> p1,pair<int,int> p2)
{
	int temp=p1.second*p2.first-p1.first*p2.second;
	if(temp==0)
		if(p1.second==p2.second)
			return p1.first<p2.first;
		else
			return p1.second<p2.second;
	else
		return (temp<=0);
	/*else if(temp>0.0)
		return 0;
	else
		return 1;*/
}

bool cmp1(pair<int,int>v1 ,pair<int,int> v2)
{
	if(v2.second==v1.second)
		return v1.first<v2.first;
	else
		return v1.second<v2.second;
}

pair<int,int> next_to_top(vector<pair<int,int> > s)
{
	pair<int,int> p1(0,0);
	if(s.size()>=2)
	{
		vector<pair<int,int> >::iterator i=s.end()-2;
		p1=*i;
	}
	return p1;
}

bool nonleftturn(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3)
{
	pair<int,int> v1(p3.first-p1.first,p3.second-p1.second),v2(p2.first-p1.first,p2.second-p1.second);
	return ((v1.first*v2.second-v1.second*v2.first)>=0);
	
}

vector<pair<int,int> > convexhull(vector<pair<int,int> > v,int n)
{
	if(v.size()<3)
	{
		if(v.size()==2 && v[1]==v[0])
			
			{
				vector<pair<int,int> > temp;
				temp.push_back(v[0]);
				return temp;

			}

		else
		{
			return v;
		
		}
	}
	vector<pair<int,int> > vertex(n);
	pair<int,int> shift=*(min_element(v.begin(),v.end(),cmp1));
	for(int i=0;i<n;i++)
	{  
		vertex[i].first=v[i].first-shift.first;
		vertex[i].second=v[i].second-shift.second;
	}
	
/*	for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first<<" "<<vertex[i].second<<endl;
	}*/
	sort(vertex.begin(),vertex.end(),cmp);
	for(int i=0;i<vertex.size();i++)
	{
		cout<<vertex[i].first+shift.first<<" "<<vertex[i].second+shift.second<<endl;
	}
		
	vector<pair<int,int> > s;
	s.push_back(vertex[0]);
	s.push_back(vertex[1]);
	s.push_back(vertex[2]);
	for(int i=3;i<n;i++)
	{
		while (s.size()>=2 && nonleftturn(next_to_top(s),s.back(),vertex[i]))
		{
			s.pop_back();
		}
		s.push_back(vertex[i]);
	}	
	for(vector<pair<int,int> >::iterator i=s.begin();i!=s.end();i++)
	{
		(*i).first+=shift.first;
		(*i).second+=shift.second;
	}
	return s;	
}

int main()
{
	int m;
	cin>>m;
	cout<<m<<endl;
	while(m--)
	{
		int n;
		cin>>n;
		vector<pair<int,int> > kingdom(n-1);
		for(int i=0;i<n-1;i++)
		{
			cin>>kingdom[i].first;
			cin>>kingdom[i].second;
		}
		int waste1,waste2,delim;
		cin>>waste1>>waste2;
		if(m!=0)
			cin>>delim;
		vector<pair<int,int> > v=convexhull(kingdom,n-1);
		cout<<v.size()+1<<endl;
		for(int i=0;i<v.size();i++)
		{
			cout<<v[i].first<<" "<<v[i].second<<endl;
		}
		cout<<v[0].first<<" "<<v[0].second<<endl;
		if(m!=0)
			cout<<delim<<endl;
	}	
	return 0;
}

[ranban282]

I TRIED ALL TEST CASES, THAY WORK, BUT I GET WA.
I HAVE EVEN REWRITTEN THE CODE.
Here goes:

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
 #include<set>
#include<complex>
using namespace std;

template  <class type1> type1 cross(const complex <type1>  &a, const complex <type1>  &b) { return imag(conj(a) * b); }

 bool cmp(const complex <int>  &a, const complex <int>  &b)
{
	if(a.imag()==b.imag())
		return a.real() <b.real();
	else
		return a.imag()<b.imag();
}

bool isequal(const complex <int>  &a, const complex <int>&b)
{
	return (a.real()==b.real() && a.imag()==b.imag());
}


template < class type1> void display(vector<complex<type1> > v){
	for(unsigned  i=0;i<v.size();i++)
	{
		cout<<v[i]<<endl;
	}

}

bool polarcmp(complex <int> a,complex<int> b)
{
	int c=cross(a,b);
	if(c>0)
		return 1;
	else 
		return 0;
		
}
template < class type1> vector<complex<type1> > convexhull(vector<complex<type1> > v)
{
	sort(v.begin(),v.end(),cmp);	
	v.erase(unique(v.begin(),v.end(),isequal),v.end());
	complex<type1> p=v[0];
	for(unsigned i=0;i<v.size();i++)
		v[i]=v[i]-=p;
	stable_sort(v.begin()+1,v.end(),polarcmp);
	vector<complex<type1> > s;
	s.push_back(v[0]);
	s.push_back(v[1]);
	for(unsigned  i=2;i<v.size();i++)
	{
		while(cross(s.back()-s[s.size()-2],v[i]-s.back())<=0)
		{
			s.pop_back();
		}
		s.push_back(v[i]);
	}
	
	for(unsigned i=0;i<s.size();i++)
	{
		s[i]+=p;
	}	
	return s;
}

int main()
{
	int k;
	cin>>k;
	cout<<k<<endl;
	while(k--)
	{	
		int n;
		cin>>n;
		vector<complex<int> > p(n);
		for(int i=0;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			complex <int> temp(x,y);
			p[i]=temp;
		}
		int delimiter;
		if(k)
		cin>>delimiter;	
		vector<complex<int> > v=convexhull(p);			
		cout<<v.size()+1<<endl;
		for(unsigned  i=0;i<v.size();i++)
		{
			cout<<v[i].real()<<" "<<v[i].imag()<<endl;
		}
		cout<<v[0].real()<<" "<<v[0].imag()<<endl;
		if(k)
			cout<<delimiter<<endl;
	}
	return 0;
}

COULD SOMEONE WITH AC PLZ PLZ GIVE ME TEST CASES OR TELL ME WHAT IS WRONG WITH THE CODE. I would be infinitely grateful to him.

[Vexorian]

I got AC after trying a lot of times, some hints:

- Sure Finding Hull precisely considering all the degeneracy is a hard task, but that is not a reason to skip the formatting of the output. Before jumping on conclusions about your convex hull finding algorithm double check that your program is using the correct I/O format. (As a matter of fact, the reason of my WA was a mistake in this area...)

- float/double arithmetic is not necessary for this problem, however this does not mean that using doubles would be a reason of WA (tested with 64bits ints and double and both give AC)

- The "only" thing you need is a correct enough convex hull implementation I used an implementation of Graham's scan that I found on the "Programming Challenges" book which is the one featured on the front page, however it had 2 modifications:

* Mine is not so "pure hardcore C" , I C++-rized it...
* The first sorting process was changed to give priority to y instead of x.

[<:3)~~]

what the output shuld be if we get colinear pts. as input

like..
0 0
1 1
2 2
0 3
0 0
???
what shuld be the hull for this??
shuld (1,1) be included?

MY SIGNATURE
*Helping others wont make u smaller!
*learn frm mistakes.

[Jan]

My code returns only 0. Since you cant find any convex hull. However, I think there is no such case.

[sv90]

need more input set

[sandy007smarty]

Hello,
I think more than one points may be repeated. If you are trying to construct the hull just by going around the edges of the given polygon and checking for correct turns then try the following case.
input:
1
9
0 0
1 2
2 1
1 1
2 0
3 1
3 3
0 3
0 0
output:
1
6
0 0
2 0
3 1
3 3
0 3
0 0

Fahim

Thank You. That is really helpful.

The history for finding O(n) algo for convex hull of a simple polygon is quite interesting. Too many intuitive algos were later proved to be incorrect. And so was mine
The best algo known for this task as of now is Melkman's Algorothm. Use it and get AC

[sazzadcsedu]

Can someone post me some critical I/O of this problem.This problem is straightforward convex hull finding,but don't know whats wrong with my code .And what eps value should be used for comparison??Tried with hundred of input,but can't find bug.

[alofa]

Why is this generating a runtime error, I have checked it character by character

Code: Select all

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
#define SQR(n) (n)*(n)

struct Point{
	int x, y;
	Point(int a = 0, int b = 0) : x(a), y(b){}
	static Point comp;
	int operator - (Point p){
		return SQR(x - p.x) + SQR(y - p.y);
	}
	bool operator < (const Point p)const{
		int left = (comp.y - y)
			* (comp.x - p.x);
		int right = (comp.y - p.y)
			* (comp.x - x);
		if (left < right) return true;
		if (left > right) return false;
		left = comp - *this;
		right = comp - p;
		if (left > right) return true;
		return false;
	}
};

Point Point::comp = Point(9999999, 9999999);

inline int area(Point &A, Point &B, Point &C){
	return A.x*(B.y - C.y) + B.x*(C.y - A.y) + C.x*(A.y - B.y);
}
vector<Point> grahamScan(vector<Point> points) {
	for (int i = 0; i < points.size(); i++) if (Point::comp.y > points[i].y ||
		(Point::comp.y == points[i].y && Point::comp.x > points[i].x))
		Point::comp = points[i];
	vector<Point> ret; ret.reserve(points.size());
	sort(points.begin(), points.end());
	ret.push_back(points.back());
	ret.push_back(points[0]);
	for (int i = 1, t = 1; i < points.size(); i++) {
		int area_ = area(ret[ret.size() - 2], ret[ret.size() - 1],
			points[i]);
		while (area_ <= 0) {
			Point a = ret[ret.size() - 2], b = ret[ret.size() - 1], c = points[i];
			if (area_ == 0 && (c.x - a.x) * (c.x - b.x) <= 0 && (c.y - a.y) * (c.y - b.y) <= 0){
				t = 0;
				break;
			}
			ret.pop_back();
			area_ = area(ret[ret.size() - 2], ret.back(), points[i]);
		}
		if (t) ret.push_back(points[i]); t++;
	}
	return ret;
}
int main(){
	int n;
	cin >> n;
	cout << n << endl;
	for (int i = 0; i < n; i++){
		int t;
		cin >> t;
		vector<Point> points;
		for (int j = 1; j < t; j++){
			int a, b;
			cin >> a >> b;
			points.push_back(Point(a, b));
		}
		cin >> t >> t;
		vector<Point> ret = grahamScan(points);
		cout << ret.size() << endl;
		for (int j = 0; j < ret.size(); j++){
			cout << ret[j].x << " " << ret[j].y << endl;
		}
		if (i < n - 1){
			cin >> t;
			cout << -1 << endl;
		}
	}
}

[brianfry713]

Use long long instead of int.
Read http://acm.uva.es/board/viewtopic.php?t=11447

[Repon kumar Roy]

I am getting Correct Output for all the inputs in the forum
But WA in verdict

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
#include <map>
using namespace std;

/*------- Constants---- */
#define MX 1000006
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define EPS 1e-9
#define PI acos(-1)

/* -------Global Variables ------ */
ll euclid_x,euclid_y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;

/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline void extended_euclid_returning_gcd(T a,T b){ if(b==0){d = a;euclid_x=1;euclid_y=0;} else {extended_euclid_returning_gcd(b, a%b);
	T x1 = euclid_y; T y1 = euclid_x - (a / b) * euclid_y ; euclid_x = x1 ; euclid_y = y1 ;}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}
template < class T > inline T mul_inv( T a , T b){T b0 = b, t, q; T x0 = 0, x1 = 1; if (b == 1) return 1;while (a > 1) { q = a / b;
        t = b, b = a % b, a = t; t = x0, x0 = x1 - q * x0, x1 = t; } if (x1 < 0) x1 += b0; return x1;
}




struct Point
{
        long long x;
        long long y;
        bool del;
        Point(){}
        bool operator == (const Point &a)
        {
                if(a.x==x && a.y==y) return 1;
                return 0;
        }
};

// A globle point needed for  sorting points with reference to the first point
// Used in compare function of qsort()
Point p0;

// A utility function to find next to top in a stack
Point nextToTop(stack<Point> &S)
{
        Point p = S.top();
        S.pop();
        Point res = S.top();
        S.push(p);
        return res;
}

// A utility function to swap two points
void swap(Point &p1, Point &p2)
{
        Point temp = p1;
        p1 = p2;
        p2 = temp;
}

// A utility function to return square of distance between p1 and p2
ll dist(Point p1, Point p2)
{
        return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
        ll  val = (q.y - p.y) * (r.x - q.x) -
        (q.x - p.x) * (r.y - q.y);
        
        if (val == 0) return 0;  // colinear
        return (val > 0)? 1: 2; // clock or counterclock wise
}

// A function used by library function qsort() to sort an array of
// points with respect to the first point
int compare(const void *vp1, const void *vp2)
{
        Point *p1 = (Point *)vp1;
        Point *p2 = (Point *)vp2;
        
        // Find orientation
        int o = orientation(p0, *p1, *p2);
        if (o == 0){
                if( dist(*p1, p0) < dist(*p2, p0) ){
                        p1->del = true;
                        return -1;
                }
                else {
                        p2->del = true;
                        return 1;
                }
        
        }
        return (o == 2)? -1: 1;
}

vector<Point> points;
int squash(int n )
{
        int i = 0, j = 0;
        for (; i < n ; i ++) {
                if(points[i].del == false ){
                        swap(points[i], points[j]);
                        j ++;
                }
        }
        return j;
}

ll check(const Point &O, const Point &A, const Point &B)
{
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
template <class T> double getdist(T a, T b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
bool comp_angle(const Point &a, const Point &b)
{
        if(check(p0, a, b) > 0)
                return true;
        else if(check(p0, a, b) == 0)
                return getdist(p0, a) < getdist(p0, b);
        return false;
}
// Prints convex hull of a set of n points.
int convexHull( int n , vector<Point > & hull)
{
        // Find the bottommost point
        ll ymin = points[0].y, min = 0;
        for (int i = 1; i < n; i++)
        {
                ll y = points[i].y;
                
                // Pick the bottom-most or chose the left most point in case of tie
                if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
                        ymin = points[i].y, min = i;
        }
        
        // Place the bottom-most point at first position
        swap(points[0], points[min]);
        
        // Sort n-1 points with respect to the first point.  A point p1 comes
        // before p2 in sorted ouput if p2 has larger polar angle (in
        // counterclockwise direction) than p1
        p0 = points[0];
        qsort(&points[1], n-1, sizeof(Point), compare);
        
        // This line gave me WA ? But don't know why >???
        n = squash(n);

        // Create an empty stack and push first three points to it.
       
        
        stack<Point> S;
        
        S.push(points[0]);
        S.push(points[1]);
        
        // Process remaining n-3 points
        for (int i = 2; i < n; i++)
        {
                // Keep removing top while the angle formed by points next-to-top,
                // top, and points[i] makes a non-left turn
                
                while (S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) !=2){
                        S.pop();
                }
                
                S.push(points[i]);
        }
        
        // Now stack has the output points, print contents of stack
        n = S.size();
        while (!S.empty()) {
                hull.push_back(S.top());
                S.pop();
        }
        return n;
}



int main()
{
        
        
        int T , n , p ;
        cin >> T;
        Point tmp;
        printf("%d\n",T);
        while (T -- ) {
                cin >> n;
                for (int i  = 0 ; i < n ; i ++ ) {
                        cin >> tmp.x >> tmp.y;
                        points.push_back(tmp);
                }
                //cin >> p   >> p;
                
                if(T) cin>>p;
                vector<Point> hull;
                int sz = convexHull( n , hull );
                cout << sz + 1 << endl;
                //cout << hull[sz -1 ].x << ' ' << hull[sz - 1].y << endl;
                for(int i = sz - 1; i >=0 ; i--)
                        cout << hull[i].x << ' ' << hull[i].y << endl;
                
                cout << hull[sz -1 ].x << ' ' << hull[sz - 1].y << endl;
                if(T) printf("-1\n");
                points.clear();
                
        }
        return 0;
        
}

This code Give me WA ?
But after removing ( n = squash(n);) I get AC
But why WA in first time ????