| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| WA 1!? | kaifonaft | 1305. Выпуклая оболочка | 18 мар 2018 02:35 | 3 |
WA 1!? kaifonaft 26 окт 2010 03:18 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 |
| Why wa#5? Help pls! | keqidei | 1305. Выпуклая оболочка | 11 ноя 2015 17:17 | 1 |
Any one who can tell me why wa#5? |
| Not cellular solution | pmartynov | 1305. Выпуклая оболочка | 5 апр 2014 20:33 | 1 |
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? |
| Some "minimal" cases... | Alex Danilyuk [SESC USU Dandelion] KTC | 1305. Выпуклая оболочка | 23 фев 2014 20:23 | 1 |
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. |
| O(n) | erfan | 1305. Выпуклая оболочка | 17 сен 2013 00:18 | 1 |
O(n) erfan 17 сен 2013 00:18 |
| Can somebody explain to me this problem? | Grebnov Ilya[Ivanovo SPU] | 1305. Выпуклая оболочка | 12 мар 2013 16:48 | 4 |
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. |
| 精度？？？？ | gaoshangbo | 1305. Выпуклая оболочка | 28 сен 2011 07:33 | 1 |
精度？？？？ gaoshangbo 28 сен 2011 07:33 |
| bad statement...hint | Hanzbrow (TNU) KCC | 1305. Выпуклая оболочка | 1 авг 2009 23:07 | 1 |
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) |
| Eeeh... Should it be convex? :) | Denis Koshman | 1305. Выпуклая оболочка | 4 авг 2008 00:40 | 3 |
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 anybody explain the problem? | Ignas | 1305. Выпуклая оболочка | 3 авг 2008 16:55 | 2 |
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 |
| Can anybody explain this to me? | Fechete Dan Ionut[dany] | 1305. Выпуклая оболочка | 3 авг 2008 16:55 | 2 |
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 |
| Test resolt | Aleksa_Markoni | 1305. Выпуклая оболочка | 7 июл 2008 07:29 | 2 |
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 |
| why wa#5? | Crash_access_violation | 1305. Выпуклая оболочка | 12 май 2008 23:21 | 2 |
why wa#5? Crash_access_violation 13 фев 2008 21:00 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. |
| What does the term "minimal by inclusion" mean?(-) | SPIRiT | 1305. Выпуклая оболочка | 11 сен 2006 15:46 | 1 |
|
| please give me some test... i think my program is right, but... | VALERO | 1305. Выпуклая оболочка | 7 авг 2006 19:53 | 1 |
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 |
| Something may help you | Yu Yuanming | 1305. Выпуклая оболочка | 12 июн 2005 12:35 | 1 |
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... |
| AAAAAAA!!!! At last!!!! I 've done it !!!. | Krayev Alexey(PSU#2) | 1305. Выпуклая оболочка | 1 апр 2005 21:32 | 1 |
|
| Help,who can give me some tests? | ABCDEFG | 1305. Выпуклая оболочка | 31 окт 2004 18:43 | 3 |
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. |
| Tests | Ronnie | 1305. Выпуклая оболочка | 29 авг 2004 04:16 | 1 |
Tests Ronnie 29 авг 2004 04:16 Anyone knows where I can find the tests to this problem? I get WA #6.
Edited by author 29.08.2004 12:53 |
