## 681 - Convex Hull Finding

**Moderator:** Board moderators

### 681 - Convex Hull Finding

I got WA many times,

Is any trap in the problen?

May the vertex be smaller than 3?

thanks~~

Is any trap in the problen?

May the vertex be smaller than 3?

thanks~~

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

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>

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

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

thx

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?

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

Thanx in advance!

Jo

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.

Thanx in advance!

Jo

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

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.

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

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