11139 - Counting Quadrilaterals
Moderator: Board moderators
11139 - Counting Quadrilaterals
I'll probably sound silly because someone solved this problem during the contest, but I am not sure how that last test case might be correct. For a 10x10 grid, there are 121 points, so even if you count degenerate cases (triangles and line segments), the result is the number of ways to choose 4 elements out of 121 which is ~8.5 mil. So the actual answer must be less than that, but it is given as ~12mil
Or I just misunderstood the problem? What does "different" mean here?
Or I just misunderstood the problem? What does "different" mean here?
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
You have to consider the concave quads as well. Consider the points
(0,0), (10, 0), (0,10) and (1,1)
They can actually create three quadrilaterals. Although according to the combination there is only 4C4=1 quads
Sorry I mistyped previously four, they actually create three quads.
(0,0), (10, 0), (0,10) and (1,1)
They can actually create three quadrilaterals. Although according to the combination there is only 4C4=1 quads
Sorry I mistyped previously four, they actually create three quads.
11139 Counting Quadrilaterals
Oh! This is a nice example of an easy-to-formulate and hard-to-solve problem. I tried it in the online contest and I wasted more than 2 hours, but yesterday I managed to finish it. Obviously, (see the ranklist) I used precomputation, I wrote a brute-force solution O(n^7) (can be O(n^6) if implemented better) that needs lots of computation time. I wonder what is the complexity of the algorithm used by other people solving the problem.
My (mixture of my colleagues and mine ideas) approach was:
- First, I count all the posibilities of selecting 4 distinct points in the grid, no 3 collinear; it is actually the number of convex quadrilaterals + 1/3 * concave quadrilaterals. It doesn't take much effort for a machine, it runs in about half a minute in my computer.
- Second, the brute-force. For each possible segment I count the points in the grid above the segment (actually the line extending the segment) and the points under it; and count the couples of points one above and one under the segment. It gives, as a result, the number of concave quadrilaterals + 2 * convex quadrilaterals.
I'd be glad to hear more ideas to solve the problem, especially those that can be implemented and precomputated during an online contest.
My (mixture of my colleagues and mine ideas) approach was:
- First, I count all the posibilities of selecting 4 distinct points in the grid, no 3 collinear; it is actually the number of convex quadrilaterals + 1/3 * concave quadrilaterals. It doesn't take much effort for a machine, it runs in about half a minute in my computer.
- Second, the brute-force. For each possible segment I count the points in the grid above the segment (actually the line extending the segment) and the points under it; and count the couples of points one above and one under the segment. It gives, as a result, the number of concave quadrilaterals + 2 * convex quadrilaterals.
I'd be glad to hear more ideas to solve the problem, especially those that can be implemented and precomputated during an online contest.
"From lost to the river" --> Spanish quote
Mine is O(n^4).
From the total total number of possible sets of 4 points (which is the binomial coefficient: (n+1)^2 choose 4), I first subtract number of sets in which four or three points are collinear (this can be done in O(n^2)).
Then for each lattice triangle (there are O(n^6) of them, but only O(n^4) different ones need to be checked -- all others can be obtained by translation), I find number p of lattice points inside it (by Pick's theorem). Number of concave quadrilaterals for which this triangle is the convex hull is 3*p. I add to the answer 2*p, because p of those quadrilaterals were already counted in the beginning.
From the total total number of possible sets of 4 points (which is the binomial coefficient: (n+1)^2 choose 4), I first subtract number of sets in which four or three points are collinear (this can be done in O(n^2)).
Then for each lattice triangle (there are O(n^6) of them, but only O(n^4) different ones need to be checked -- all others can be obtained by translation), I find number p of lattice points inside it (by Pick's theorem). Number of concave quadrilaterals for which this triangle is the convex hull is 3*p. I add to the answer 2*p, because p of those quadrilaterals were already counted in the beginning.
Last edited by mf on Tue Oct 24, 2006 4:55 pm, edited 1 time in total.
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
If you use pick's theorem in this problem then solution can be much faster. Did you try to use it
.
Actually I was so fed up with in finding efficient solution that when I found it I did not care to optimize much. I split the problem into some parts:
a) Find all concave quadrilaterals in efficient manner.
b) Find C(n,4).
c) Find the zero area quads and the triangles that was counted as quads.
Then use some inclusion exclusion. Not posting the details or it will be an spoiler.

Actually I was so fed up with in finding efficient solution that when I found it I did not care to optimize much. I split the problem into some parts:
a) Find all concave quadrilaterals in efficient manner.
b) Find C(n,4).
c) Find the zero area quads and the triangles that was counted as quads.
Then use some inclusion exclusion. Not posting the details or it will be an spoiler.
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
I think me and mf were almost concurrent in posting time and use similar methods.
Wow, great!, your solutions are more than enough for me, they completely satisfy my curiosity. In fact I remember thinking about using Pick in the contest for a second, as everybody usually does when faces a problem with lattice and figures, but I didn't know how to apply it (it was before I needed to count only the concave or convex ones
)

"From lost to the river" --> Spanish quote
I follow the algorithm described above, but got WA.
the maximum input is n = 120, right?
please verify my output for n = 118,119 and 120:
118 2691512617349032
119 2877994834324016
120 1085980800144653612
Is it correct? if yes, why do I get WA then? any idea?
Thanks
the maximum input is n = 120, right?
please verify my output for n = 118,119 and 120:
118 2691512617349032
119 2877994834324016
120 1085980800144653612
Is it correct? if yes, why do I get WA then? any idea?
Thanks
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
Thanks for the quick reply.
It seemed that I got overflow just for the nCk[n^2][4].
I just got it AC, thanks.
Btw, is there anyone can solve this problem without pre-calc?
Or this problem was designed to be solved by precalculation?
It seemed that I got overflow just for the nCk[n^2][4].
I just got it AC, thanks.
Btw, is there anyone can solve this problem without pre-calc?
Or this problem was designed to be solved by precalculation?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
Need to find a O(n^3) algorithm if you want to do it without pre-calculation. My O(n^4) gets tle if I don't do pre-calculation. It needs a bit of optimizing to pass the time limit.
Last edited by sclo on Fri Nov 03, 2006 1:52 am, edited 2 times in total.