难道是是因为用stl的原因
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <cmath>
using namespace std;
class point
{
public:
	int x;
	int y;
	point(int x,int y):x(x),y(y)
	{
		;
	}
	point()
	{
		;
	}
	friend bool operator <(const point &a,const point &b);
	friend int direct(point &a,point & b,point & c);
	friend double length(point &a,point &b);

	static point base;

};
class Vector
{
public:
	int x;
	int y;
	Vector(const point& a,const point& b)
	{
		this->x=b.x-a.x;
		this->y=b.y-a.y;
	}
	int lengthsquar()
	{
		return this->x*this->x+this->y*this->y;
	}
	int cross(Vector & b)
	{
		return (this->x*b.y)-(this->y*b.x);
	}
};

int direct(point &a,point & b,point & c)
{
	Vector start(a,b),end(a,c);
	int dir=start.cross(end);
	if(dir<0)
	{
		//right
		return 2;
	}
	if(dir>0)
	{
		//left
		return 1;
	}
	if(0==dir)
	{
		return 0;
		//middle
	}
}

double length(point &a,point &b)
{
	return sqrt( (double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}

bool operator <(point &a,point &b)
{
	Vector va(point::base,a);
	Vector vb(point::base,b);
	int temp=va.cross(vb);
	if(temp==0)
	{
		return va.lengthsquar()<vb.lengthsquar();
	}
	else
	{
		return temp>0;
	}
}
point point::base(0,0);




int main()
{
	int n,around;
	cin>>n>>around;
	int i=n,j;
	vector<point> vertice(1001);
	vertice.clear();
	point input;
	while(i--)
	{
		cin>>input.x>>input.y;
		vertice.push_back(input);
	}
	point min(vertice[0]);
	for(vector<point>::iterator iter=vertice.begin(); iter!=vertice.end(); iter++)
	{
		if(iter->y<=min.y)
		{
			if(iter->y==min.y)
			{
				min.x = iter->x<min.x?iter->x:min.x;
			}
			else
			{
				min=*iter;
			}
		}
	}
	point::base = min;
	sort(vertice.begin(),vertice.end());
	vector<point> convex(1001);
	convex.clear();
	for( i=0; i<3; i++)
	{
		convex.push_back(vertice[i]);
	}
	//i 是当前要测试是否加入凸包的点在vertice的下标
	i=3;
	j=convex.size()-1;
	while(i<vertice.size())
	{
		if(1==direct(convex[j-1],convex[j],vertice[i]))
		{
			convex.push_back(vertice[i]);
			i++;
		}
		else
		{
			convex.pop_back();
		}
		j=convex.size()-1;
	}
	double sum=0;
	vector<point>::iterator start,end;
	for(end=start=convex.begin(),end++; end!=convex.end(); start++,end++)
	{
		sum+=length(*start,*end);
	}
	sum+=length(convex[convex.size()-1],convex[0]);
	sum+=3.141592653*2*around;
	cout<<fixed<<setprecision(0)<<sum<<endl;

	
}

• Re:graham居然超时了？吐血求指导 (2831) 6363817 2013-02-27 14:30:03
  • Re:graham居然超时了？吐血求指导 (40) 6363817 2013-02-27 14:31:35