【POJ 1113】Wall

http://poj.org/problem?id=1113

夏令营讲课时的求凸包例题，据说是PKUSC2015的一道题

我WA两次错在四舍五入上了(=ﾟωﾟ)ﾉ

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

double Pi = acos(-1);

const int N = 1003;

struct Point {

	double x, y;

	Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}

	bool operator < (const Point &A) const {

		return x == A.x ? y < A.y : x < A.x;

	}

} a[N], tu[N];

int top = 1;

Point operator + (Point a, Point b) {return Point(a.x + b.x, a.y + b.y);}

Point operator - (Point a, Point b) {return Point(a.x - b.x, a.y - b.y);}

Point operator * (Point a, double x) {return Point(a.x * x, a.y * x);}

Point operator / (Point a, double x) {return Point(a.x / x, a.y / x);}

double Dot(Point a, Point b) {return a.x * b.x + a.y * b.y;}

double Cross(Point a, Point b) {return a.x * b.y - a.y * b.x;}

double sqr(double x) {return x * x;}

double dis(Point a, Point b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}

int dcmp(double x) {return fabs(x) < 1e-8 ? 0 : (x < 0 ? -1 : 1);}

void mktb(int n) {

	tu[1] = a[1];

	for(int i = 2; i <= n; ++i) {

		while (top > 1 && dcmp(Cross(a[i] - tu[top], tu[top] - tu[top - 1])) <= 0) --top;

		tu[++top] = a[i];

	}

	int k = top;

	for(int i = n - 1; i >= 1; --i) {

		while (top > k && dcmp(Cross(a[i] - tu[top], tu[top] - tu[top - 1])) <= 0) --top;

		tu[++top] = a[i];

	}

}

int main() {

	int n, l;

	scanf("%d%d", &n, &l);

	for(int i = 1; i <= n; ++i) scanf("%lf%lf", &a[i].x, &a[i].y);

	sort(a + 1, a + n + 1);

	mktb(n);

	double ret = 2.0 * l * Pi;

	for(int i = 1; i < top; ++i)

		ret += dis(tu[i], tu[i + 1]);

	printf("%d\n", (int) (ret + 0.5));

	return 0;

}

复习模板~