My function returns the same truth value regardless of what order the four points are in.
Yes, this was my intent.
My code was often called “obfuscated” even when I tried otherwise, so I gave up on readability. :smack: Still, I find my C code more readable than Lance’s Mathematica. 
struct xy { double x, y; };
/* can the points p0, p1, p2, p3 form a convex quadrilateral? */
is_cvx_quad(struct xy *p0, struct xy *p1, struct xy *p2, struct xy *p3)
{
#define NR(p,q,r) \
((p->x - q->x) * (r->y - p->y) > (r->x - p->x) * (p->y - q->y))
return 1 ^ NR(p0,p1,p2) ^ NR(p1,p2,p3) ^ NR(p2,p3,p0) ^ NR(p3,p0,p1);
}
Hmmm…
We’re doing something similar but I am computing the direction of 12 cross products where you seem to be doing only four. Furthermore, I think you get different answers for (0,0), (0,1), (-1,0), (0,-1) versus (0,-1), (-1,0), (0,1), (0,0).
I can’t think of a faster way to do this than Lance’s solution, so my service to the thread is to un-obfuscate his code 
The basic idea is that a quadrilateral is convex as long as each point lies outside the triangle formed by the other three. So the code does exactly that, using a crossproduct-based “in triangle” test. Each test requires three cross products, hence 12 crossproducts.
If the points were ordered, you do it quickly by just going through the points and checking for sign changes in the difference from one point to the next (e.g. from (1,1)->(3,4)->(1,7) x is +, then - so 1 sign change; y is + and + so 0 sign changes). A convex polygon will have only two sign changes on a circuit.
(Completing with (2,3) makes x go +, then -, then +, 3 total changes. With (0,3) you get -, +, +, for only two. In both cases y goes -, -, + giving two total). The nice thing is this works for any polygon.
But I gather that’s not the problem presented. If for some reason multiplication was super expensive you could solve it by finding all the orderings and doing this test, but I think the cross product method is the best for this one.
I’m having difficulty understanding the method you are describing here. Could you describe in detail how it would work for, e.g., (0, 0) -> (3, 0) -> (2, 2) -> (0, 3) [and then back to (0, 0)] vs. (0, 0) -> (3, 0) -> (1, 1) -> (0, 3) [and then back to (0, 0)]? The first of these is convex and the second is non-convex, but the sign change patterns seem the same to me.
Neat, huh?
One way to think of it is that there are five classes of ordered quadruplets; the count of successes (0, 1, 2, 3, or 4) from the four comparisons determine which of those five classes the ordered quadruplet is in. The even-numbered counts are convex.
The five classes are
[ul]
[li] (0) convex quadrilateral, vertexes in counter-clockwise order[/li][li] (1) concave quadrilateral, vertexes in counter-clockwise order[/li][li] (2) convex quadrilateral, vertexes out of order[/li][li] (3) concave quadrilateral, vertexes in clockwise order[/li][li] (4) convex quadrilateral, vertexes in clockwise order[/li][/ul]
Note that the out-of-order case (edges overlapping) occurs only for convex quadrilaterals; a concave quad is always “in order,” or rather the 3 permutations give 3 different concave quadrilaterals.)
When my “users” present me with an angle of exactly 180 degrees, and ask me if it’s more or less than 180, they don’t care what answer I give! Maybe your users are pickier! (And, unless Mathematica uses unlimited precision, I’d assume you could provoke a similar problem in your code by substituting x=0.0000000001 or some such for x=0 in your counterexample.)
Here’s another Doper with septimus set to Ignore this User. He must be a right-winger.
Accidentally hit tab-enter. Ignore this post.
septimus, I still think you are ignoring the class of, “not a quadrilateral”, but this is a set of measure zero so depending on circumstances it may not be important.
I’ll propose a new problem. How many ways can I form a line of zero or more pennies, nickels, and dimes so that the total is $1.00? Keep in mind that order matters so nine dimes followed by ten pennies is distinct from ten pennies followed by nine dimes.
There are 915 ways to form such a line so that the total is $0.25.
septimus: Ooh, nice. That’s clever.
Lance: Here’s an off-the-top-of-my-head-and-hence-untested simple attempt at your code:
Edit: wait: small bug. Fixing now.
Here’s the fixed version:
long total = 0;
for (int dimes = 0; dimes <= 10; dimes++) {
for (int nickels = 0; nickels <= 20 - 2*dimes; nickels++) {
int pennies = 100 - 10*dimes - 5*nickels;
int coins = pennies + nickels + dimes;
total += fact(coins)/(fact(pennies)*fact(nickels)*fact(dimes));
}
}
int numways(int resid)
{
return resid < 0 ? 0 :
resid == 0 ? 1 :
numways(resid - 1) + numways(resid - 5) + numways(resid - 10);
}
main() { printf("%d
", resid(100)); }
A version that’s somewhat faster than my previous. 
(Untested; I don’t even know if the answer fits in ‘int.’)
int numways(int resid)
{
static int memo[101];
return resid < 0 ? 0 :
resid == 0 ? 1 :
memo[resid] ? memo[resid] :
(memo[resid] = numways(resid - 1) + numways(resid - 5)
+ numways(resid - 10));
}
main() { printf("%d
", resid(100)); }
I think septimus gets the correct answer of 8437020668201 while MilTan does not, but I’m not 100% sure since neither of you posted your answers.
No, I don’t get the right answer. I’m trying to figure out why at the moment.
I think you’re calculating partitions of 100 into 1’s, 5’s, and 10’s as opposed to compositions. 9 dimes followed by 10 pennies is distinct from 10 pennies followed by 9 dimes.
Well, the factorial stuff is supposed to take care of that. In that situation, I’m finding the permutations of all 19 coins (= fact(coins)) and dividing out the ones that only differ in the orders of the pennies, or the orders of the dimes. At least, that’s what I’m supposed to be doing.
Ok, I see that now. Is it possible that theanswerr is too big to fit in a long? Do you get 915 when you try to calculate the $0.25 case?
At this point, I think my solution is conceptually correct, but is being foiled by the (obvious in retrospect) overflow caused by factorial. Point goes to septimus, for a solution that doesn’t require BigNums
Edit: Lance: Unfortunately, 25! is also too large to fit in a long. I do get the right answer with $0.10, though, for what it’s worth 
The recursive formula that septimus used is the clever answer I was looking for, but I agree that your answer is conceptually correct. I never think about bignums since I work in Mathematica.