(A computer-rendered image by my company)
Hello, everyone! My name is Rujia Liu. I used to do a lot of problem solving and problemsetting, but after graduated from Tsinghua University, I'm spending more and more time on my company ?
(You may realized that the paragraph above is copied from the texts of my 3rd contest, but that's me, lazy me.)
This time, my contest is all about geometry and computer graphics (CG). This is a bit strange, since I'm a bit weak in geometry during my "programming contest career". However, my company, www.qeyj.com "forced" me to write a lot of codes for 3dsmax, AutoCAD, developed some real-time 3D applications, and even our own off-line render (that's why I wrote problem M and N!). As a result, I'm getting more and more familiar with geometry and CG and finally decided to arrange this contest.
This contest is partially educative. I'm trying to cover a lot of important areas of geometry and CG, so the problems themselves are not very imaginative. Nevertheless, some of the problems (like problem N) are still attractive (at least to me), so try your best to enjoy the contest!
However, I believe this contest is hard, not only for most (if not all!) contestants, but also for myself. I mean, geometry codes can be very error-prone, so I'm NOT 100% sure that there's no mistake in the judge data (though I've spent a looooot of time to prevent such things). Don't hesitate to write emails to me (rujia.liu@gmail.com) during the contest if you suspect the judge data might be wrong (or suffered from floating-point issues). The best way is to email me your solution, and then I'll check ASAP.
This is an Internet contest, so don't forget that you can always use google. I will NOT be angry if you use codes from someone else. That's also a way to learn. However, please try to google formulae, ideas and algorithms only, and write your own code. That's best for you.
F. Polishing a Extruded Polygon
H. Smallest Enclosing Rectangle
Here is the whole Problemset(PDF), and the Gift Package.
I'm trying my best to reduce potential floating-point issues by carefully designing the test cases and allowing some difference between your output and the standard one, and the margins are always quite generous. If your programs still suffer from these kinds of errors, it usually means that they are numerically instable. Please redesign your algorithm or refactor your code.
I know that geometry problems can be very difficult to debug, even if you're given the judge data! Thus, I decided to provide some additional data and debugging tools that make your life (a little bit) easier. You can download them on the contest website.
I'd like to thank Yiming Li for validating problem A, B, C and M, Yi Chen and Di Tang for validating problem E, Yeji Shen and Dun Liang for discussing and validating other problems.