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

miko'mized
New poster
Posts: 8
Joined: Thu Dec 04, 2003 4:56 pm
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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
yes My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

miko'mized
New poster
Posts: 8
Joined: Thu Dec 04, 2003 4:56 pm
[; I fixed it , but still doesn't work.

WA WA WA WA...

so frustrating.

miko'mized
New poster
Posts: 8
Joined: Thu Dec 04, 2003 4:56 pm
wyvmak wrote: 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
New poster
Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong
Contact:
miko'mized wrote: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
New poster
Posts: 1
Joined: Tue Jan 13, 2004 10:06 am
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
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

### 681 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
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China
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
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm
Enlightening! CLR says this:
(if more than one point has the same angle, remove all but the one that is farthest from p0)
What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.
Alan J. Perlis

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### WA after repeated tries

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;
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);
stack<point> r;
r.push(t);
r.push(t);
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
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm
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;
vector < PI >::iterator VIT=V.begin();
VIT++;
sort(VIT,V.end(),compare_angle());
V.push_back(F);
hull=V;
hull=V;
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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
2nibbler & 2eduard:

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

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

### Compiler error but works on g++

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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
You're trying to use scanf and printf without having included cstdio header file.