Project Euler Forum

Hello,
the 177 statement is not clear for me.
The question sais: "What is the total number of non-similar integer angled quadrilaterals?"
What does non-similar means? Let's make an example:
Let's call the four angles a,b,c,d, as the angles that you see looking towards vertex A,B,C,D.
If those angles were e.g. a=80, b=70, c=110 and d=100, we would have a convex quadrilateral.
Now suppose I can get a combination of inner angles out of it that satisfies the condition, having all inner angles integer, but suppose that there is also another combination (e.g. stretching the quadrilateral in one dimensions) that preserves the angles a,b,c,d but changes the 8 inner angles, and suppose this combination is good too. Do I have to count both of these solutions or just one?
Also, what about rotations? A quadrilateral with angles a=70, b=110, c=100 and d=80 (i.e. a rotation of my example) would it be considered similar or not?
Also, another question (maybe a stupid one).
We have an error bound of 10^-9. What if I change a good combination of just about 10^-12? All other angles would change accordingly to that, and probably they would still be integer. Giving this little change another valid combination, aren't those infinite?
1.00000000001 is different from 1.00000000002 and 1.00000000003 and 1.00000000004 and so on. All of them evaluate to 1 since they are well beyond the error bound, but they are all different...
Sorry if I made stupid questions, but I really need a clarification to solve this one.
Cheers,
sfabriz

If the four complete angles are equal, but the 'corner angles', i.e. the angles between a side and a diagonal are different, the two figures are not similar, thus there are several nonsimilar integer-angled rectangles. Quadrilaterals which are the same up to rotations, reflections or dilations are similar, so all squares are (integer-angled and) similar. cf. also http://en.wikipedia.org/wiki/Similarity_(geometry)

The error bound refers to calculated angles, I expect you'd start out by selecting a handful of angles, these must of course be exact integers. From those angles you calculate the remaining angles. If an angle calculated (by a sensible formula and supposing a non-freakish floating point unit) is within 10^-9 of an integer, it actually is an integer.

All right, back on work then.
Thank you very much.
sfabriz

do quadrilaterals where some of the corner angles are 0 count?

No, do not consider degenerate cases.

Hm, then I think the text needs a minor change. (add the word strictly)
A simple polygon is strictly convex if every internal angle is strictly less than 180 degrees.

But would a quadrilateral with an interior angle of 180 degrees not be a triangle instead of a quadrilateral?
Or do I miss something?

Yes, it would be a triangle and hence it is not to be considered.
Also, you must not include in your solution angles of 0 degrees.

Cheers
sfabriz

And to respond to henk263, if you're considering a convex quadrilateral, it means that you must consider a poly with 4 sides. If one angle would be 180° then the number of sides gets lowered of one unit, so when you reach 180° you don't have a quadrilateral any more, hence you must discard that possibility.

Cheers again,
sfabriz

hk wrote:But would a quadrilateral with an interior angle of 180 degrees not be a triangle instead of a quadrilateral?
Or do I miss something?

Isn't a triangle a special quadrilateral? I solved the problem now though, so thanks for answering my question

There are definitions of polygons under which a tetragon may have a 180° angle, but as far as I know, a quadrilateral always has angles other than 180°.

I'm not 100% sure what the meaning of the word "similar" applies to in this problem. Would the following quadrilaterals be considered similar or not?

QUAD: 3,3,177,177 (bottom left, bottom right, upper left, upper right)

(DAC,CAB,DBA,CBD - ADB,BDC,ACD,ACB)
#1: (2,1,1,2 - 176,1,1,176)
#2: (1,2,2,1 - 175,2,2,175)

They both form the same "outer" angles for a quadrilateral, but have different inner angles.

Nevermind, answer is no, they are not similar. Solved the problem though...

Concerning similarity of rectangles in euler 177 (integer angled polygons):
Please confirm that similar is to be understood that a
rectangle with angles a b c d can be also similar to one with angles
d c b a (inversely similar).

Groetjes Albert

Please don't create a new topic for a problem for which a topic already exists.
Perhaps reading through previous posts will help somewhat.

Can anyone confirm whether the answer is greater than 100,000,000? (My answer is much greater than 100,000,000 and if that is wrong then I'm probably misunderstanding the problem or something)

Jamie wrote:Can anyone confirm whether the answer is greater than 100,000,000? (My answer is much greater than 100,000,000 and if that is wrong then I'm probably misunderstanding the problem or something)

That is way too large. It is less than 10^6.

jaap wrote:

Jamie wrote:Can anyone confirm whether the answer is greater than 100,000,000? (My answer is much greater than 100,000,000 and if that is wrong then I'm probably misunderstanding the problem or something)

That is way too large. It is less than 10^6.

Thanks, I think I figured out a very wrong assumption, and are now getting results that seem less than 10^6.

Can somebody confirm the total number of integer angled quadrilaterals (similar quads are counted as distinct) to be <removed by moderator>? Thank you.

EDIT: Solved. I hope it won't be considered as giving out too much - the last four digits of the total number of integer angled quadrilaterals (with similar quads counted as distinct) are indeed <....>.

<Edited to remove the numbers.>
I've written 2 programs months apart to solve this problem, both of these get <number deleted> as the answer but Euler doesn't agree this is the right answer. I've counted analytically the number of solutions that are Cyclic Quadrilateral (opposite angles add up to 180 degrees) and the number that are Kites, these being <number deleted> and <number deleted> respectively and these are the number my programs get (45 of these solutions being both cyclic and a kite). Can anyone else suggest anything else I can do to debug my program.