计算几何模板

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

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

 

# 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()$)

192.168.1.1 说:
2022年8月10日 01:48

Do you own a router or modem, then you might have heard about the term Internal configuration and router configuration which are very important to do when you first buy a new router or when you have just reset a router. 192.168.1.1 Frankly speaking, there are hundreds of router brands across the world and every one of them has high end router models that have a different configuration process. But the most common thing among the router can be the Internet Protocol which the normal users can access when their router is connected perfectly in hardware configuration.


登录 *


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