我贴下我代码？我就是用Gram扫描法求解的！怎么老师超时呢？崩溃了
//功能：利用graham扫描法求凸包问题
//思想：先找出最左下角的点设其为P0，根据幅脚判排列除p0以外的点，然后p1入栈,扫描线在2->n扫，如果是栈顶和栈顶的
//      下一个元素以及扫描线所在的点连成的线段构成凸包那么扫描线所在的点压入栈，若是凹包，那么当前栈顶退栈，
//      扫面点继续停留在原来那个点，再判断栈顶及栈顶下一个元素及扫描点所在位置，看是否构成凸包，若是扫面点入栈，
//      否则退栈.
//

#include<stdio.h>
#include<iostream>
#include<stack>
using namespace std;
#include<cmath>
#include<algorithm>
using namespace std;

#define pi acos(-1.0)
#define max 100000 
struct point
{
	int x;
	int y;
};

point startpoint;

double cross_douct(point a,point b,point c)
{
   point v1,v2;
   v1.x=c.x-a.x;
   v1.y=c.y-a.y;
   v2.x=b.x-a.x;
   v2.y=b.y-a.y;
   return v1.x*v2.y-v2.x*v1.y;
}
double dist(point p1,point p2)
{
	return sqrt(((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))*1.0);
}

bool sortbyangle(point b,point c)//传值分别是栈顶元素下一个元素，栈顶元素，扫描线所在的点
{
	double d=cross_douct(startpoint,b,c);
//	cout<<"*"<<d<<"*"<<endl;
	if(d>0) return true;
	else if(d<0) return false;
	else if(dist(startpoint,b)<=dist(startpoint,c))
	  return true;
	else
		return false;
}


int main()
{
 point p[100];
 stack<point> convex_hull;
 int n,L;
 while(scanf("%d%d",&n,&L)!=EOF)//输入是多少个顶点的点集
 {
 for(int i=0;i<n;i++)
	 scanf("%d %d",&p[i].x,&p[i].y);
 //寻找最右下角的顶点
 point p0=p[0];
 //cout<<p0.x<<p0.y<<endl;
 //cout<<p[0].x<<p[0].y<<endl;
 int k=0;//记录最小顶点的位置
 for(int j=1;j<n;j++)
 {
	 if((p[j].y<p0.y)||(p[j].y==p0.y&&p[j].x<p0.x))
	 {
		 p0.x=p[j].x;
		 p0.y=p[j].y;
		 k=j;
	 }
 }
 startpoint.x=p0.x;
 startpoint.y=p0.y;
 for(int i=1;i<n;i++)
 {
	 double temp=cross_douct(p0,p[i],p[i+1]);
	 if(temp==0&&p[i].x<p[i+1].x)
	 {
		 p[i].x=max;
		 p[i].y=max;
	 }
 }
sort(p,p+n,sortbyangle);
convex_hull.push(p[0]);
if(p[1].x!=max&&p[1].y!=max)
   convex_hull.push(p[1]);
for(int l=2;l<n;)//栈顶的下一个元素怎么取值？
{ 
   if(p[l].x==max&&p[l].y==max)
   {
	     l++;
		 continue;
	 
   }
   	point top=convex_hull.top();
	convex_hull.pop();
    point top_next;
	if(!convex_hull.empty())
    top_next=convex_hull.top();
    else
    top_next=top;
	convex_hull.push(top);
	double h=cross_douct(top_next,top,p[l]);//判断栈顶下一个元素，栈顶，以及扫描点是否构成凸包的问题
	 //p0,p1,p2
	if(h<0) 
	{
       //	if(convex_hull.size()!=1)
          convex_hull.pop();
      //  else
      //   l++;
		  
	}
	else 
    //是凸包，则当前扫描点进入队列，扫描点移下下一个顶点
	{  
       if(h>0)
        {
              convex_hull.push(p[l]);
              l++;
        }
       else if(dist(top_next,top) < dist(top_next,p[l]))
       	{
               if(convex_hull.size()!=1)
				  convex_hull.pop();
               convex_hull.push(p[l]);
               l++;
        }
     	else
          	l++;
	}
}
//cout<<"-4"<<endl;
double d_sum=0;
int size=convex_hull.size();
point first=convex_hull.top();
point last=convex_hull.top();
while(!convex_hull.empty())//打印
{
	
	//cout<<"0"<<endl;
	point temp=convex_hull.top();
//	cout<<"1"<<endl;
	//cout<<last.x<<" "<<last.y<<endl;
   //	cout<<temp.x<<" "<<temp.y<<endl;
    d_sum=d_sum+dist(last,temp);
//	cout<<d_sum<<endl;
	//cout<<"2"<<endl;
	last=temp;
	convex_hull.pop();
}
//cout<<last.x<<last.y<<endl;
//cout<<first.x<<first.y<<endl;
if(size!=2)
  d_sum=d_sum+dist(last,first);
//cout<<d_sum<<endl;
 d_sum=d_sum+2*L*pi;
//cout<<d_sum<<endl; 
printf("%d\n",int(d_sum+0.5));
 }
	return 0;
}

• Re:怎么老是超时啊？求大人救助 (3739) laicb 2011-06-03 15:01:46