----------------------------------- HeavenAgain Tue Nov 06, 2007 5:15 pm ccc stage 2 Q#1 ----------------------------------- does anyone know how to approach the CCC stage 2 first problem? cows (see problem below)? the maximum area is a bit hard to find.... i mean, there are a few dozen of different shapes it might create, how do we know what points to take. any ideas? Cows Input file: "cows.in" Output: to standard output "cows.out" Your friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Given the locations of some trees, you are to help farmers try to create the largest pasture that is possible. Not all the trees will need to be used. However, because you will oversee the construction of the pasture yourself, all the farmers want to know is how many cows they can put in the pasture. It is well known that a cow needs at least 50 square metres of pasture to survive. Input The first line of input contains a single integer, n (1 ≤ n ≤ 10000), containing the number of trees that grow on the available land. The next n lines contain the integer coordinates of each tree given as two integers x and y separated by one space (where -1000 ≤ x, y ≤ 1000). The integer coordinates correlate exactly to distance in metres (e.g., the distance between coordinate (10, 11) and (11, 11) is one metre). Output You are to output a single integer value, the number of cows that can survive on the largest field you can construct using the available trees. Sample Input 4 0 0 0 101 75 0 75 101 Output for Sample Input 151 ----------------------------------- octopi Tue Nov 06, 2007 5:26 pm Re: ccc stage 2 Q#1 ----------------------------------- http://marknelson.us/2007/08/22/convex/ ----------------------------------- HeavenAgain Tue Nov 06, 2007 5:30 pm RE:ccc stage 2 Q#1 ----------------------------------- the hull in state is really amazing :| i can stare at it for hours. thank you for showing me this, thanks! ----------------------------------- octopi Tue Nov 06, 2007 5:40 pm Re: ccc stage 2 Q#1 ----------------------------------- That article should be a start, however it will still be tricky to compute the area of the object you obtain. ----------------------------------- HeavenAgain Tue Nov 06, 2007 5:43 pm RE:ccc stage 2 Q#1 ----------------------------------- yeah, i figured out how to do the area, the problem was finding the right shape, now thats out of the way, thanks :D something new today! ----------------------------------- octopi Tue Nov 06, 2007 8:01 pm Re: ccc stage 2 Q#1 ----------------------------------- Ya, I only knew about hulls because a friend of mine had to do an assignment (3rd year COSC at brock) involving them last week. Its pretty interesting stuff though. ----------------------------------- Tony Tue Nov 06, 2007 8:25 pm RE:ccc stage 2 Q#1 ----------------------------------- Heh, we did convex hulls in first year Eng @ Waterloo ;) Apparently they give a decently good heuristic for the Travelling Salesman Problem. ----------------------------------- HeavenAgain Wed Nov 07, 2007 4:30 pm RE:ccc stage 2 Q#1 ----------------------------------- This problem made me love triangles so much now or there is a better/faster way to find a triangle's area? ----------------------------------- CodeMonkey2000 Wed Nov 07, 2007 5:37 pm RE:ccc stage 2 Q#1 ----------------------------------- Wow this problem is tough. How do they expect us to figure this out? ----------------------------------- zylum Wed Nov 07, 2007 8:26 pm RE:ccc stage 2 Q#1 ----------------------------------- convex hull is a common problem. if you make ccc stage 2 then it should be pretty easy for you.. ----------------------------------- CodeMonkey2000 Wed Nov 07, 2007 8:57 pm RE:ccc stage 2 Q#1 ----------------------------------- This isn't even high school level material...or is it? ----------------------------------- Nick Wed Nov 07, 2007 8:59 pm RE:ccc stage 2 Q#1 ----------------------------------- i was just reading a thread about the ccc this is stage 2 which is only for senoirs which means they must be in highschool, have a knowledge of c/c++/java or some other language i dont quite remember also they must have more than 1 cs credit to meet the requirement above they SHOULD be able to figure this out, however it might take a while ----------------------------------- CodeMonkey2000 Wed Nov 07, 2007 9:03 pm RE:ccc stage 2 Q#1 ----------------------------------- I'm in grade 11 now. I took grade 11 compsci last year, and we only did nested looping and string manipulation in pascal. The grade 12's just did OOP in java. I checked out out some other questions from stage 2, I have the general idea on how to go about doing them but this one has me stumped :S ----------------------------------- HeavenAgain Wed Nov 07, 2007 11:11 pm RE:ccc stage 2 Q#1 ----------------------------------- I think this is one of the easiest one for stage two, that is, if you understood how to use some advanced (common) algorithm, and a lot of math ----------------------------------- Clayton Wed Nov 07, 2007 11:35 pm RE:ccc stage 2 Q#1 ----------------------------------- The fact of the matter is, is that the people that advance to Stage 2 are the people that take their learning into their own hands. Honestly, there's no way that you're going to learn almost any of this in high school, so you're going to have to do it yourself. ----------------------------------- Tony Wed Nov 07, 2007 11:48 pm RE:ccc stage 2 Q#1 ----------------------------------- Indeed. Stage 2 invites about 20 top students from the senior CCC. While this is definitely well above the common high school material, it's not that far fetched for Stage 2 contestants to be familiar with this.