## 681 - Convex Hull Finding

Moderator: Board moderators

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### A probable common mistake

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

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

I got many wa.
can any one give me test cases
Sleep enough after death, it is the time to work.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Ok, that's just spamming... please stop doing that.

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### This problem is driving me nuts!

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
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### WHY WA???

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
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### IT SEEMS NO ONE WANTS TO HELP

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My code returns only 0. Since you cant find any convex hull. However, I think there is no such case.
Ami ekhono shopno dekhi...
HomePage

sv90
New poster
Posts: 17
Joined: Wed Feb 01, 2006 8:27 pm

### more test case

need more input set

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
fmannan wrote: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

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 681 - Convex Hull Finding

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.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

alofa
New poster
Posts: 2
Joined: Mon Sep 30, 2013 12:52 am

### 681 - Convex Hull Finding

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 681 - Convex Hull Finding

Use long long instead of int.
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 681 - Convex Hull Finding

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 ????