tubag.cpp

凸包算法的实现

#include <iostream.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define eps 1e-9
/*class Point
{
   public:
	   void set(double ix,double iy)
	   {
		   x=ix;
		   y=iy;
	   }
	   double xOffset()
	   {
		   return x;
	   }
	   double yOffset()
	   {
		   return y;
	   }
	   double angle()
	   {
		   angl=atan2(y,x);
		   return angl;
	   }
   protected:
	   double x;
	   double y;
	   double angl;
};
*/

struct Point
{
	double x;
	double y;
	
};
/*
double multiply(Point p1,Point p2,Point p0)
{
	return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));	
};

double distance(Point p1,Point p2)
{
	return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));	
};*/
/*pointset为输入的点集；
  ch为输出的凸包上的点集，按照逆时针方向排列;
  n为pointset中的点的数目
  len为输出的凸包上的点的个数
*/
/*
void Graham(Point pointset[],Point ch[],int n,int &len)
{
	int i,j,k=0,top=2;
	Point tmp;
	/*选取pointset中y坐标最小的点pointset[k]，如果这样的点有多个，则取最左边的一个*/
/*	for(i=1;i<n;i++)
		if ((pointset[i].y<pointset[k].y)||((pointset[i].y==pointset[k].y)&&(pointset[i].x<pointset[k].x)))
	    k=i;
	tmp=pointset[0];
	pointset[0]=pointset[k];
	pointset[k]=tmp; /*现在pointset中y坐标最小的点在pointset[0]*/
/*	for (i=1;i<n-1;i++) /*对顶点按照相对pointset[0]的极角从小到大进行排序，极角相同的按照距离pointset[0]从近到远进行排序*/
/*	{	
		k=i;
		for (j=i+1;j<n;j++)
			if ( (multiply(pointset[j],pointset[k],pointset[0])>0)
			     ||(( fabs(multiply(pointset[j],pointset[k],pointset[0]))<eps)
			      &&(distance(pointset[0],pointset[j])<distance(pointset[0],pointset[k])) )
			   ) 
			   k=j;
		tmp=pointset[i];
		pointset[i]=pointset[k];
		pointset[k]=tmp;
	}
	ch[0]=pointset[0];
	ch[1]=pointset[1];
	ch[2]=pointset[2];	
	for (i=3;i<n;i++)
	{
		while (top>0 && multiply(pointset[i],ch[top],ch[top-1])>=0) top--;
		ch[++top]=pointset[i];
	}
	len=top+1;
};
*/
void main()
{
  // strand(time(0));
	int n;
	cout<<"please input a number: ";
	cin>>n;

	Point p[3];


}