681 - Convex Hull Finding

[miko'mized]

hm maybe that's wrong ... for this test:
1
7
0 6
-4 4
-6 2
-2 -2
0 -4
1 -4
4 4
anwser is:
1
7
0 -4
1 -4
4 4
0 6
-4 4
-6 2
0 -4

right?

[..]

yes

[miko'mized]

[; I fixed it , but still doesn't work.

WA WA WA WA...

so frustrating.

[miko'mized]

when i implemented Graham scan, i used the following points to check my Graham scan:

1
15 // number of points
0 0
0 1
0 2
0 3
0 4
1 3
2 2
3 3
4 4
4 3
4 1
4 0
3 0
2 0
1 0

i hope that can help.

Mind one thing... in 681 problem given input is naturaly sorted so we needn't to do that again. I think your sample is incorrect according to program input.

[raymond85]

hm maybe that's wrong ... for this test:
1
7
0 6
-4 4
-6 2
-2 -2
0 -4
1 -4
4 4
anwser is:
1
7
0 -4
1 -4
4 4
0 6
-4 4
-6 2
0 -4

right?

I am afraid that the test case itself is not correct.

Since all the shapes are closed contours, therefore, the last vertex should be identical to the first vertex.

However, in your test case, the first and the last vertex aren't the same. Anyway, I am still getting WA with Graham Scan.

[fmannan]

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

[sunhong]

I've got TLE,RE and WA 10+ times,but haven't got AC!
Can anyone give me some hint or test data so I can find what is wrong
int my program? Thank you!
I try to extend the array to store the points but still got wa!
What is the special judge data of this problem?

[sunhong]

Can someone give me a code of this problem?
Thanks! I've tried every possible way to fix
my mistake but still get WA!!

[Examiner]

Enlightening! CLR says this:

(if more than one point has the same angle, remove all but the one that is farthest from p0)

[abishek]

Code: Select all

[cpp]

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct point 
{
    int x, y;
    point (int a=0, int b=0):x(a),y(b){}
    int operator*(const point &b)
	{
	    return x*b.y-y*b.x;
	}
    point operator-(const point &b)
	{
	    return point(x-b.x,y-b.y);
	}
};

int main()
{
    int k, n;
    cin>>k;
    cout<<k<<endl;
    while(k--)
    {
	vector<point> t;
	point s;
	cin>>n;
	for(int i=1; i<n; i++)
	{
	    cin>>s.x>>s.y;
	    t.push_back(point(s.x,s.y));
	}
	int wa;
	cin>>wa>>wa>>wa;
	int m=0;
	point mi=t[0];
	for(int i=1; i<t.size(); i++)
	{
	    if(t[i].y<mi.y)
	    {
		mi.x=t[i].x;
		mi.y=t[i].y;
		m=i;
	    }
	    else if(t[i].y==mi.y)
	    {
		if(t[i].x<mi.x)
		{
		    mi.x=t[i].x;
		    m=i;
		}
	    }
	}
	vector<point> z;
	for(int i=m; i<t.size(); i++)
	    z.push_back(t[i]);
	for(int i=0; i<m; i++)
	    z.push_back(t[i]);
	t=z;
	t.push_back(t[0]);
	stack<point> r;
	r.push(t[0]);
	r.push(t[1]);
	for(int i=2; i<t.size();)
	{
	    if(r.size()==1)
	    {
		r.push(t[i]);
		i++;
		continue;
	    }
	    point p=r.top(); r.pop();
	    point next=r.top(); r.push(p);
	    int val=((next-p)*(p-t[i]));
	    if(val>=0) // changed it to val>0 (still WA)
	    {
		r.push(t[i]);
		i++;
	    }
	    else
	    {
		r.pop();
	    }
	}
	vector<point> ans(r.size());
	while(!r.empty())
	{
	    ans[r.size()-1]=r.top();
	    r.pop();
	}
	cout<<ans.size()<<endl;
	for(int i=0; i<ans.size(); i++)
	    cout<<ans[i].x<<" "<<ans[i].y<<endl;
	if(k)
	    cout<<-1<<endl;
    }
    return 0;
}
[/cpp]

I have tried sorting according to polar angle and then took up the advice of some one on the board and tried to take the input as it is. I Still get WA. can someone help me?

thx
abi

[nibbler]

I used Grahm's scan and got WA. With almost identical code I passed convex hull problem on USACO. I've checked test cases posted above, works fine. Anyone has an idea about where the error might be? Any new test data?

Code: Select all

// FINDING THE COMPLEX HULL USING GRAHM'S  SCAN 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <iterator>
#include <cstdlib>
#include <cmath>
#define EPS 0.0000001
#define PI pair < int ,int  >
using namespace std;

PI F;

double dist(PI A,PI B) {	// Returns squared distance
	return 1.0*(A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

double sta(PI A,PI B,PI C) {
return 0.5*(A.first*B.second-A.second*B.first + A.second*C.first - A.first*C.second + B.first*C.second - C.first*B.second ) ;
}

class compare_angle {
		public:	
	bool operator() (PI A,PI B) {		
	if (fabs(sta(F,A,B))<EPS)
		if (dist(F,A)<dist(F,B)) return 1; else return 0;
	else
		if (sta(F,A,B)>EPS) return 1; else return 0;	
	}
};

class pair_compare {
	public:
	bool operator() (PI A,PI B) {
		if (A.second==B.second) return A.first<B.first;
		else return A.second<B.second;
	}		
};

void output(vector <PI> & Q) {
	Q.push_back(Q.front());	
	printf ("%d\n",Q.size());
	for (int i=0;i<Q.size();i++) 
		printf ("%d %d\n",Q[i].first,Q[i].second);
}

int main() {
	int test_cases,temp;
	scanf ("%d",&test_cases);
	printf ("%d\n",test_cases);
	for (int t=0;t<test_cases;t++) {
		vector < PI > V;
		vector < PI > hull;
		int N;
		if (t!=0) scanf ("%d",&temp);
		scanf ("%d",&N);
		V.resize(N);
		hull.resize(N);
		for (int i=0;i<N;i++) 
			scanf ("%d %d",&V[i].first,&V[i].second);
		// Sort and remove duplicates
		sort(V.begin(),V.end(),pair_compare());
		V.resize(distance(V.begin(),unique(V.begin(),V.end())));
		N=V.size();
		if (N<=4) {
			output(V);	
		} else {
			// Sort according to angle
			F=V[0];	
			vector < PI >::iterator VIT=V.begin();
			VIT++;
			sort(VIT,V.end(),compare_angle());
			V.push_back(F);
			hull[0]=V[0];
			hull[1]=V[1];
			int top=1,i=2;
			while (i<=N)
				if (sta(hull[top-1],hull[top],V[i])<EPS)
					top--;
				else {
					top++;
					hull[top]=V[i];
					i++;
				}		
			hull.resize(top);
			output(hull);	
			if (t!=test_cases-1) printf ("-1\n");
		}		
	}	
	return 0;
}

[Eduard]

I'm olso getting WA for this problem and I'm going crazy because my program answers right to all of my tests and tests which I find in this page.I use Graham's Algorithm for finding Convex Hull and also solve (with the same programm(with some little changes)) problem 10065.
Please somebody give me some good tests.
Thanks.

[BiK]

2nibbler & 2eduard:

Don't use floating point arithmetic. You can do everything with integer arithmetic.

[temper_3243]

Here is my perfect g++ code for convex hull 681.
It compiles fine on my cygwin and g++ -Wall gives no warnings.
But the judge gives me compile error.Here is the source.


http://rafb.net/paste/results/3Go0wv77.txt

[Krzysztof Duleba]

You're trying to use scanf and printf without having included cstdio header file.