I can vouch for the Stillwell's one : Mathematics and Its History, and here's why:
unlike most math history books which are, well, focused on the history alone,
Stillwell's focus on the math.
That is, it's not about the mathematicians, but about the mathematics.
Each chapter deals with a math topic
(be it pythagorean triples, analytic geometry, etc)
and it even has exercises to help you get an idea on what the main involved ideas are.
each chapter has a supplement showcasing one or two biographies about the main mathematicians involved on the chapter's subject
But the real feature, again, it's that the book is structured focusing on the mathematics history, not the mathematicians history (hence its title)
There's also an oldie but goodie:
2 volume set Eves' Great Moments in Mathematics , part of the Dolciani Mathematical Expositions series
vol1 : before 1650
vol2 : after 1650
here each chapter is devoted to help you know about a specific mathematical breakthrough and why it's important on the mathematics development
This one starts talking about the Ishango Bone, which is dated around 10 tousand years ago, given you want to go far back as possible
I would highly recommend the book "Concrete Mathematics" by Oren Patashnik, Donald E. Knuth and Ronald L. Graham.
I don't know that it exactly fits your criteria—or rather, I don't know that every reader would agree that it fits your criteria—but in my opinion, it does.
The first chapter, for instance, discusses three well-known puzzles of the type that will be addressed by the techniques to be taught in the book. Each puzzle is presented in its entirety before any approach to solving it is discussed.
The book requires VERY active reading, and if you just sit back passively without making your own efforts to solve each problem as you come to it rather than after reading the entire chapter, you will probably end up completely lost. ;)
What I would recommend for reading this book is that you:
- Play with each problem as you encounter it, before reading further.
- Once you have either solved the problem or gotten as far as you can without help, read a few more paragraphs (or even just one more paragraph).
- Play with the new ideas and approaches presented in that paragraph. See if you make any discoveries about them on your own.
- Repeat.
The nice thing is that the discussion of the puzzles and the exploratory discoveries from each extend far beyond just the direct solution to the puzzle itself. So exploration is very definitely encouraged.
One more note: I highly recommend you read the preface before you start in at Chapter 1. It will make certain conventions clearer; for example, it will explain why there are comments from students of the course scattered throughout the book. :)
An excerpt from the preface (my favorite part of the preface, actually):
The course title “Concrete Mathematics” was originally intended as an antidote to “Abstract Mathematics,” since concrete classical results were rapidly being swept out of the modern mathematical curriculum by a new wave of abstract ideas popularly called the “New Math.” Abstract mathematics is a wonderful subject, and there’s nothing wrong with it: It’s beautiful, general, and useful. But its adherents had become deluded that the rest of mathematics was inferior and no longer worthy of attention. The goal of generalization had become so fashionable that a generation of mathematicians had become unable to relish beauty in the particular, to enjoy the challenge of solving quantitative problems, or to appreciate the value of technique. Abstract mathematics was becoming inbred and losing touch with reality; mathematical education needed a concrete counterweight in order to restore a healthy balance.
And another excerpt from the preface, one which (for me at least) shows very clearly that this is "my kind of book":
Some people think that mathematics is a serious business that must always be cold and dry; but we think mathematics is fun, and we aren’t ashamed to admit the fact. Why should a strict boundary line be drawn between work and play? Concrete mathematics is full of appealing patterns; the manipulations are not always easy, but the answers can be astonishingly attractive.
Best Answer
User161303 has listed very good sources. I want to share my experience about preparing for contests involving Geometry.
The Art and Craft of Problem Solving by Paul Zeitz
I do not feel that it is elementary at all though good part of it is very nice introduction to geometry especially for people getting started with geometry for contests.
Geometric Transformations I, Geometric Transformations II, Geometric Transformations III, and Geometric Transformations IV by I. M. Yaglom
Geometric transformations are extremely powerful tools that come in very handy in solving some of the very hard Geometry problems of the IMO kind.
Problems on Plane Geometry, by Viktor Prasolov
It is freely available if you google for it. It has problems ranging from easy to mighty hard problems. It has solutions as well.