凸包问题： 定义：对于平面上一个点的有限集合，如果以集合中任意两点P和Q为端点的线段上的点都属于该集合，则称该集合是凸集合。 一个点集S的凸包是包含S的最小凸集合，其中，最小是指S的凸包一定是所有包含S的凸集合的子集。 对于平面上n个点的集合S，它的凸包就是包含所有这些点（或者在内部，或者在边界上）的最小凸多边形，最小凸多边形上的点称为凸包的极点。
#include<iostream> using namespace std; void ConvexHull(int x[],int y[],int n) { int i,j,k,sign1,sign2; int A,B,C; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { sign1=0;sign2=0; A=y[i]-y[j]; B=x[j]-x[i]; C=x[i]*y[j]-x[j]*y[i]; for(k=0;k<n;k++) { if(k!=i&&k!=j) { if(A*x[k]+B*y[k]+C>0) sign1=1; else sign2=1; if(sign1==sign2) break; } } if(k==n) cout<<"("<<i<<","<<j<<")"<<endl; } } int main() { int x[1000],y[1000]; int n; cin>>n; for(int i=0;i<n;i++) cin>>x[i]>>y[i]; ConvexHull(x,y,n); return 0; }