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

hoshiko
New poster
Posts: 2
Joined: Mon Nov 05, 2001 2:00 am
Contact:

### 681 - Convex Hull Finding

I got WA many times,
Is any trap in the problen?
May the vertex be smaller than 3?

thanks~~

New poster
Posts: 3
Joined: Mon Nov 05, 2001 2:00 am
This problem may be solved using Jarvis march, for example. One thing you should notice is that the first vertex is repeated twice, in the begin and in the end of the description of the polygon.
On 2001-11-05 07:38, hoshiko wrote:
I got WA many times,
Is any trap in the problen?
May the vertex be smaller than 3?

thanks~~

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
you also can use Graham Scan to solve it ..

I think the n >= 3, for I didn't care about it ...

you should notice that ..

1. for each test case of input ...
your output should contain -1 at the end, except the last case ...

2. there will be no three points in the same line.

<font size=-1>[ This Message was edited by: Even on 2001-11-22 14:39 ]</font>

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

### 681 Convex Hull Finding help~

Is there any special data or special conditions need to be checked??

I always get WA with a program which can do the convex hull problems correctly for other c.h. problems.

thx

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
seems the output has some requirements, maybe you re-check your output format? i don't think your c.h. will have problem.

ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am

### 681

Hi.....

are there any special case to look out for in the input cases??
i keep getting WA...

can n <= 3?

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i think the test cases are all with n>=3, don't worry about n<3
maybe check your data output format, as you have to output smallest Y first?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Hi, as wyvmak said, all cases are of n >= 3.

pay attention to the cases when many points are collinear~

ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am
im not too clear about the line in the problem statement saying tat
no neighbouring points are collinear..... wats does neighbouring mean exactly?

anyhow, im using jarvis march.... when points are collinear, the one with the greatest length is chosen, tat should be correct rite?

im starting the algo at smallest y value......
and outputing the vertices in clockwise order....

hmm... or maybe the output vertices should juz be sorted by their y value??
is tat wat u mean?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Yup, as the output specification states that the points of the convex hull starts at the point with the smallest y-coordinate.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### Can figure out what is wrong....

Hi! I'm just trying to solve this problem for a few days and I can't figure out what's wrong with my solution....
I'm using graham scan and when it finishes I go on on the resulting polygon to find out if there exists any colinear points, if they exist I eliminate the one in the center, i.e. I leave only the two on the corners!

Is there any trick data? If u cold give me some input output it would be of great help.

Jo

ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am
hi!

you can check out the link http://icpc.cc.ntu.edu.tw/ncpc1998/problems/
but even though i manage to get the same output for the data set provided im still geting WA.....

its weird......

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i think i used Graham scan, too. i think the bug may be in the implementation, I/O etc. as a normal implementation of this algorithm should be able to solve any tricky cases, unless... (i think it's not likely that the output would only be 2 points, ie. the input points lies on a straight line only)

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.

for neighbouring, it may mean the next or previous point in the input. but i think if you ignore this statement and implement one that can tackle this, not only you'll solve this problem, but also it'll be useful for many other problems involving convex hull, eg. 10002.

ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am
im able to solve tat case also........
but still WA....... its screwed....

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### Yet getting WA

Hi, again...

My algorithm solved the ncpc data set and wyvmak's input too, but I'm still getting WA!

So, if someone here did solved this problem and got AC with graham scan, I will be glad to see how u did implemented it. If u can send me just the part of the code wich compute the graham scan of the polygon, I will be thankful, and I think the people wich participates of this forum would be too...

Thanx!
Jo