> 难道是是因为用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居然超时了？吐血求指导 (40) 6363817 2013-02-27 14:31:35