Secure Multi-party Computation (SMC) has been a research forcus in international cryptography community in recent years. SMC deals with the following situation: Two (or many) parties want to jointly perform a computation without disclosing their private inputs. Privacy-preserving convex hulls problem is a special case of SMC and it can be applied in many fields such as military and commercial fields. In this paper, we first present two privacy-preserving protocols to solve the convex hulls problem by using Yao's millionaire protocol. We also discuss the security. correctness and performance of the two protocols. Based on the Euclid-distance Measure Protocol, an approximate solution to the convex hulls problem is proposed for fairness, which conceals more private information.