1605.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1605 on 2006-02-25 at 17:59:58 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 1024;

class Point {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
	void update(const Point& p) { x -= p.x; y -= p.y; }
	bool operator <(const Point&) const;
	bool operator !=(const Point& p) const { return y*p.x != x*p.y; }
	double dis(const Point& p) const { return sqrt(1.0*(x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)); }
};
bool Point::operator <(const Point& p) const {
	if(y*p.x != x*p.y) return y*p.x < x*p.y;
	else return x*x+y*y > p.x*p.x+p.y*p.y;
}

int main()
{
	Point v[MAX];
	int stack[MAX], n, l, i;
	
	while(scanf("%d %d", &n, &l) != EOF) {
		for(i = 0; i < n; i++) v[i].make();
		int lo = 0, vn = 2;
		for(i = 1; i < n; i++)
			if(v[i].y < v[lo].y) lo = i;
		for(i = 0; i < n; i++) 
			if(i != lo) v[i].update(v[lo]);
		v[lo].update(v[lo]); swap(v[lo], v[0]); sort(v+1, v+n);
		for(i = 2; i < n; i++)
			if(v[i] != v[i-1]) v[vn++] = v[i];
		int top = 0;
		for(i = 0; i < 3; i++) stack[top++] = i;
		for(i = 3; i < vn; i++) {
			while(true) {
				int a = stack[top-1], b = stack[top-2];
				if((v[a].x-v[b].x)*(v[i].y-v[a].y)-(v[i].x-v[a].x)*(v[a].y-v[b].y) > 0) break;
				top--;
			}
			stack[top++] = i;
		}
		double total = l * M_PI * 2;
		for(i = 0; i < top; i++) 
			total += v[stack[i]].dis(v[stack[(i+1)%top]]);
		printf("%.0lf\n", total);
	}
	
	return 0;
}