1. there are always solutions.
2. convex polygon. but don't need to find.

Edited by author 10.12.2005 05:18

Hey can you give me an idea of using convex polygons for this problem??

I solved it in O(n^2), tho it can be done in O(nlogn), but none of my solutions uses convex hulls...