OJ Board

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

thanks~~

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

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>

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

seems the output has some requirements, maybe you re-check your output format? i don't think your c.h. will have problem.

Hi.....

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

can n <= 3?

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?

Hi, as wyvmak said, all cases are of n >= 3.

pay attention to the cases when many points are collinear~

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?

Yup, as the output specification states that the points of the convex hull starts at the point with the smallest y-coordinate.

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

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

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.

im able to solve tat case also........
but still WA....... its screwed....

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