681

hoshiko · Post by **hoshiko** » Mon Nov 05, 2001 8:38 am

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

thanks~~

sadoc · Post by **sadoc** » Mon Nov 05, 2001 2:46 pm

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 · Post by **Even** » Thu Nov 22, 2001 3:38 pm

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 · Post by **10153EN** » Sun May 19, 2002 9:52 pm

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 · Post by **wyvmak** » Mon May 20, 2002 8:35 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 · Post by **ngchumin** » Sun Jun 16, 2002 12:01 pm

Hi.....

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

can n <= 3?

wyvmak · Post by **wyvmak** » Sun Jun 16, 2002 4:04 pm

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 · Post by **10153EN** » Sun Jun 16, 2002 4:11 pm

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

pay attention to the cases when many points are collinear~

ngchumin · Post by **ngchumin** » Sun Jun 16, 2002 5:58 pm

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 · Post by **10153EN** » Sun Jun 16, 2002 6:27 pm

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

jpfarias · Post by **jpfarias** » Mon Jun 17, 2002 3:56 am

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

ngchumin · Post by **ngchumin** » Mon Jun 17, 2002 4:26 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 · Post by **wyvmak** » Mon Jun 17, 2002 4:39 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 · Post by **ngchumin** » Mon Jun 17, 2002 10:32 am

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

jpfarias · Post by **jpfarias** » Mon Jun 17, 2002 9:42 pm

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

OJ Board

681 - Convex Hull Finding

681 - Convex Hull Finding

681 Convex Hull Finding help~

Can figure out what is wrong....

Yet getting WA