681 - Convex Hull Finding

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

A probable common mistake

Post by Ndiyaa ndako » Tue Jul 12, 2005 3:13 pm

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:

681 please test cases

Post by 898989 » Fri Aug 04, 2006 10:24 pm

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Aug 04, 2006 11:39 pm

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!

Post by ranban282 » Fri Sep 01, 2006 5:09 pm

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

Post by ranban282 » Wed Sep 06, 2006 12:05 am

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

Post by ranban282 » Sat Oct 21, 2006 1:59 pm

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

Post by Vexorian » Wed Feb 21, 2007 6:11 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

Post by <:3)~~ » Sat Mar 10, 2007 7:34 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Mar 10, 2007 9:49 am

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
Location: Dhaka,Bangladesh

more test case

Post by sv90 » Thu Apr 19, 2007 7:34 pm

need more input set

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Location: Hyderabad
Contact:

Post by sandy007smarty » Thu Sep 13, 2007 8:06 pm

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 :)

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

681 - Convex Hull Finding

Post by sazzadcsedu » Sat Sep 11, 2010 8:34 am

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
For Hints: http://salimsazzad.wordpress.com

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

681 - Convex Hull Finding

Post by alofa » Mon Sep 30, 2013 12:58 am

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

Post by brianfry713 » Tue Oct 01, 2013 11:28 pm

Use long long instead of int.
Read http://acm.uva.es/board/viewtopic.php?t=11447
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

Post by Repon kumar Roy » Fri Dec 26, 2014 8:43 pm

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

Post Reply

Return to “Volume 6 (600-699)”