|
|
first test is not sample. Edited by author 26.10.2010 19:06 The test has only one point. and it is far away from 0 Any one who can tell me why wa#5? Hey guys, I ACed with a cellular automata (a grid of 1000x1000 and a set of rules to transform 0s -> 1s). But is there any other(faster?) way to find a 45 convex hull given a set of points without a cellular automata? What should I do if the hull consist of one or two points? For example, test 1 1 1 Obviously, answer is 1 1 But these "three" points lie on one line. What sequence of broken line’s vertexes should print my program? Give me some hints or tests. Just find a convex octagon of minimal area which satisfyes the following conditions: - all the points given are inside it or lay on it's borders - it's 2 sides are parallel to oX (-) - it's 2 sides are parallel to oY (|) - it's 2 sides are 45 degrees to oX (/) - it's 2 sides are -45 degrees to oX (\) And then output all the vertices of this figure. There could be 8 vertices, but some of them might be the same (some sides has zero length), so output them only once. So your output is from 1 till 8 vertices. Very easy statistical solution is O(N) time, O(1) memory. P.S. I will answer any your question - just mail me. I can only understand the problem statement after reading this thread... Thanks so much! Just find a convex octagon of minimal area Area should not be minimal, the number of points inside convex polygon should be minimal, in other words, try so that more points lie on the boundary rather than inside the polygon. I've never seen such a bad statement. if you have n points and you are asked to make a convex hull it is normal to think, that it can contain ONLY THESE points. hint: convex hull can contain any points, but number of vertices should be minimal as well as square) I think yes, but it's not clear from problem statement despite the name of this set. In russian it is said: "Правильной выпуклой оболочкой множества M называется минимальное по включению выпуклое множество.." I think that english statement is wrong.. Can you tell me if the required "well" convex hull can have points not from the set M? Thank you. Yes, and generally it will Well-formed convex hull of set M is minimal (relative to inclusion) set, containing M Minimal area Edited by author 03.08.2008 16:55 Please can someone tell me what is the answer for this test: 8 1 3 2 2 3 1 4 2 5 3 4 4 3 5 2 4 3.000000 5.000000 1.000000 3.000000 3.000000 1.000000 5.000000 3.000000 I use Grakham algorithm and got WA#5... Please anyboby give me some tests... thanks... Me too got WA#5... Can somebody help pls? I dont see the problem. Could it be vertecs on the same line. i have wa on 3-rd test... If you can, tell me please how can i remember the first point? thank you... [code deleted] Edited by author 07.08.2006 19:54 Edited by moderator 08.08.2006 17:35 Algo is O(n) The ans may not be more than 8 points,it is easy to see :) If all points on one line, I output the two ends of it. Maybe there isn't such test, because I think one line is not closed... At least, my pro got AC... sorry ,no problem now. Edited by author 31.10.2004 18:45 Is the coordinates integer or real? Warning!!!!!!!!!!!!! Everybody who see this should notice that if there's only one vertex,you should output it's coordinate. Anyone knows where I can find the tests to this problem? I get WA #6. Edited by author 29.08.2004 12:53 |
|
|