计算几何模板

tonyfang posted @ 2015年8月27日 19:48 in math with tags c++ math , 431 阅读

今天打的计算几何模板,包含很多内容,具体见模板啦

 

# include <stdio.h>
# include <math.h>
# include <vector>
# include <algorithm>

using namespace std;

const double eps = 1e-10,
             pi = acos(-1.0);

inline double abs(double a) {
	return a<0 ? -a : a;
}

inline double max (double a, double b) {
	return a>b ? a : b;
}

inline double min (double a, double b) {
	return a<b ? a : b;
}

inline double add(double a, double b) {
	if (abs(a + b) < eps * (abs(a) + abs(b))) return 0;
	return a + b;
}

inline bool iszero(double x) {
	return abs(x) < eps;
}

struct P {
	double x, y;
	P() {}
	P(double x, double y) : x(x), y(y) {}
	P operator + (P p) {
		return P(add(x, p.x), add(y, p.y));
	}
	P operator - (P p) {
		return P(add(x, -p.x), add(y, -p.y));
	}
	P operator * (double d) {
		return P(x * d, y * d);
	}
	double dot(P p) {
		return add(x * p.x, y * p.y);
	}
	double det(P p) {
		return add(x * p.y, -y * p.x);
	}
};

inline double dist2(P a, P b) {
	return (a - b).dot(a - b);
}

inline double dist(P a, P b) {
	return sqrt(dist2(a, b));
}

//等于0:三点共线
//大于0:p0p2在p0p1的逆时针方向
//小于0:p0p2在p0p1的顺时针方向 
inline double direction(P p1, P p2, P p0) {
	return (p1-p0).det(p2-p0);
}

inline bool dots_inline(P p1, P p2, P p3) {
	return iszero(direction(p1,p2,p3));
} 

//q是否在线段p1p2上 
inline bool on_seg(P p1, P p2, P q) {
	return dots_inline(p1, p2, q) && (p1-q).dot(p2-q) <= 0;
} 

//p1p2与q1q2的交点 
inline P intersection(P p1, P p2, P q1, P q2) {
	return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}

inline bool cmp_x(const P& p, const P& q) {
	return p.x < q.x || (p.x == q.x && p.y < q.y);
}

inline bool segintersection(P p1, P p2, P q1, P q2) {
	double d1 = direction(p1, q1, q2), 
		   d2 = direction(p2, q1, q2),
		   d3 = direction(q1, p1, p2),
		   d4 = direction(q2, p1, p2);
	if(d1 * d2 < 0 && d3 * d4 < 0) return true;
	else if (d1 == 0 && on_seg(q1, q2, p1)) return true;
	else if (d2 == 0 && on_seg(q1, q2, p2)) return true;
	else if (d3 == 0 && on_seg(p1, p2, q1)) return true;
	else if (d4 == 0 && on_seg(p1, p2, q2)) return true;
	return false;
}

#define PB push_back
 
inline vector <P> convexhull(vector<P> ps) {
	int n = ps.size();
	sort(ps.begin(), ps.end(), cmp_x);
	int k = 0;
	vector<P> qs(n * 2);
	for (int i = 0; i < n; ++i) {
		while (k > 1 && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1])<=0) --k;
		qs[k++] = ps[i];
	} 
	for (int i = n - 2, t = k; i >= 0; --i) {
		while (k > t && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1])<=0) --k;
		qs[k++] = ps[i];
	}
	qs.resize(k - 1);
	return qs;
}

inline double rotating(vector<P> ps) {
	vector<P> qs = convexhull(ps);
	int n = qs.size();
	if (n == 2) return dist(qs[0], qs[1]);
	int i = 0, j = 0;
	for (int k = 0; k < n; ++k) {
		if(! cmp_x(qs[i], qs[k])) i = k;
		if(cmp_x(qs[j], qs[k])) j = k;
	}
	double res = 0;
	int si = i, sj = j;
	while(i != sj || j != si) {
		res = max(res, dist(qs[i], qs[j]));
		if ((qs[(i + 1) % n] - qs[i]).det(qs[(j + 1) % n] - qs[j]) < 0) i = (i + 1) % n;
		else j = (j + 1) % n; 
	}
	return res;
}

inline double area(vector<P> ps) {
	double res = 0;
	int N = ps.size();
	for (int i = 0; i < N; ++i) {
		int nt = (i+1) % N;
		res += ps[i].det(ps[nt]);
	} 
	res = abs(res / 2.0);
	return res; 
}

inline void prtP(P a) {
	printf("(%lf,%lf)", a.x, a.y);
}

int main() {
	
	return 0;
}

用模板过了些题目啦

$poj 2187$旋转卡壳(模板中的$rotating()$)

$poj 3348$凸包面积(求凸包,模板中的$convexhull()$,求面积$area()$)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter