ccc stage 2 Q#1

[HeavenAgain]

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]

http://marknelson.us/2007/08/22/convex/

[HeavenAgain]

the hull in state is really amazing i can stare at it for hours.
thank you for showing me this, thanks!

[octopi]

That article should be a start, however it will still be tricky to compute the area of the object you obtain.

[HeavenAgain]

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]

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]

Heh, we did convex hulls in first year Eng @ Waterloo Apparently they give a decently good heuristic for the Travelling Salesman Problem.

[HeavenAgain]

This problem made me love triangles so much now
or there is a better/faster way to find a triangle's area?

[CodeMonkey2000]

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

[zylum]

convex hull is a common problem. if you make ccc stage 2 then it should be pretty easy for you..

[CodeMonkey2000]

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

[Nick]

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]

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]

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]

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.