Author 
Message 
HeavenAgain

Posted: Tue Nov 06, 2007 5:15 pm Post subject: 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 





Sponsor Sponsor



octopi





HeavenAgain

Posted: Tue Nov 06, 2007 5:30 pm Post subject: 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

Posted: Tue Nov 06, 2007 5:40 pm Post subject: 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

Posted: Tue Nov 06, 2007 5:43 pm Post subject: 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 something new today! 





octopi

Posted: Tue Nov 06, 2007 8:01 pm Post subject: 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

Posted: Tue Nov 06, 2007 8:25 pm Post subject: 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. 
Tony's programming blog. DWITE  a programming contest. 




HeavenAgain

Posted: Wed Nov 07, 2007 4:30 pm Post subject: 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? 





Sponsor Sponsor



CodeMonkey2000

Posted: Wed Nov 07, 2007 5:37 pm Post subject: RE:ccc stage 2 Q#1 


Wow this problem is tough. How do they expect us to figure this out? 





zylum

Posted: Wed Nov 07, 2007 8:26 pm Post subject: 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

Posted: Wed Nov 07, 2007 8:57 pm Post subject: RE:ccc stage 2 Q#1 


This isn't even high school level material...or is it? 





Nick

Posted: Wed Nov 07, 2007 8:59 pm Post subject: 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

Posted: Wed Nov 07, 2007 9:03 pm Post subject: 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

Posted: Wed Nov 07, 2007 11:11 pm Post subject: 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

Posted: Wed Nov 07, 2007 11:35 pm Post subject: 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. 





