计算几何模板

本文主要是介绍计算几何模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

总模板

#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#define point Vector
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
const double eps = 1e-8;   
struct Vector {
	double x, y; 
	Vector(double X = 0.0, double Y = 0.0){
		x = X, y = Y; 
	} 
}; 
int dcmp(double x) { 
	if(fabs(x) < eps) 
		return 0;   
	return x < 0 ? -1 : 1; 
}
bool operator < (const point &a, const point & b) {
	if(dcmp(a.x - b.x) == 0) 
		return a.y < b.y; 
	else return a.x < b.x; 
}
bool operator == (const point &a, const point & b) {
	if(dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0) 
		return true; 
	return false; 
} 
Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }    
Vector operator - (Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }  
Vector operator * (Vector a, double p) { return Vector(a.x * p, a.y * p); } 
Vector operator / (Vector a, double p) { return Vector(a.x / p, a.y / p); } 
double dot(Vector a, Vector b) {
	return a.x * b.x + a.y * b.y; 
}
double len(point a) {
	return sqrt(dot(a, a)); 
}
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));     
}
// b 在 a 的逆时针为正，夹角为 a 转到 b 的有向角度（sin)   
double cross(Vector a, Vector b) {
	return a.x * b.y - a.y * b.x; 
}
// 求点积再除以模长.   
double Angle(Vector a, Vector b) {
	return acos(dot(a, b) / len(a) / len(b)); 
}
// 求法向量.    
Vector normal(Vector a) {
	double u = len(a);   
	return Vector(-a.y / u, a.x / u); 
}        
// 看 tmp 是否在 ab 上
int Onsegment(point tmp, point a, point b) {  
	if(dcmp(cross(a - tmp, b - tmp)) == 0 && dcmp(dot(a - tmp, b - tmp)) <= 0)
		return 1;
	return 0; 
}
// 前面是线段上，后面是不在线段上相交.  
int Line_Intersect(point a, point b, point c, point d) {   
	double x1 = cross(b - a, c - a), y1 = cross(b - a, d - a);  
	double x2 = cross(d - c, a - c), y2 = cross(d - c, b - c);   
	if(!dcmp(x1) || !dcmp(x2) || !dcmp(y1) || !dcmp(y2)) {
		bool f1 = Onsegment(a, c, d); 
		bool f2 = Onsegment(b, c, d); 
		bool f3 = Onsegment(c, a, b); 
		bool f4 = Onsegment(d, a, b); 
		bool f = (f1 | f2 | f3 | f4); 
		return f;   
	}
	if(dcmp(x1) * dcmp(y1) < 0 && dcmp(x2) * dcmp(y2) < 0) 
		return 1; 
	return 0; 
}

凸包

#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#define point Vector
#define ll long long 
#define N  200009 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;
const double eps = 1e-8;      
struct Vector {
	double x, y; 
	Vector(double X = 0.0, double Y = 0.0){
		x = X, y = Y; 
	} 
}; 
int dcmp(double x) { 
	if(fabs(x) < eps) 
		return 0;   
	return x < 0 ? -1 : 1; 
}   
bool operator < (const point &a, const point & b) {
	if(dcmp(a.x - b.x) == 0) 
		return a.y < b.y; 
	else return a.x < b.x; 
}
bool operator == (const point &a, const point & b) {
	if(dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0) 
		return true; 
	return false; 
} 
Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }    
Vector operator - (Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }  
Vector operator * (Vector a, double p) { return Vector(a.x * p, a.y * p); } 
Vector operator / (Vector a, double p) { return Vector(a.x / p, a.y / p); } 
double dot(Vector a, Vector b) {
	return a.x * b.x + a.y * b.y; 
}
double len(point a) {
	return sqrt(dot(a, a)); 
}
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));      
}
// b 在 a 的逆时针为正，夹角为 a 转到 b 的有向角度（sin)   
double cross(Vector a, Vector b) {
	return a.x * b.y - a.y * b.x; 
}              
int n ; 
point p[N], A[N]; 
bool cmp2(point i, point j) {
	int t = dcmp(cross(i - p[1], j - p[1]));    
	if(t != 0) 
		return t > 0; 
	else {
		return dis(i, p[1]) < dis(j, p[1]); 
	}   
}    
int main() {
	// setIO("input");   
	scanf("%d", &n); 
	for(int i = 1; i <= n ; ++ i) {
		scanf("%lf%lf", &p[i].x, &p[i].y); 
		// if(p[i].y < p[1].y) swap(p[i], p[1]); 
	}      
	sort(p + 1, p + 1 + n);   
	sort(p + 2, p + 1 + n, cmp2);  
	int cnt = 1; 
	A[1] = p[1]; 
	for(int i = 2; i <= n ; ++ i) {   
		while(cnt > 1 && dcmp(cross(A[cnt] - A[cnt - 1], p[i] - A[cnt])) != 1)        
			-- cnt ; 
		A[++ cnt] = p[i];       
	}
	A[++ cnt] = p[1];   
	double ans = 0.0;             
	for(int i = 1; i < cnt ; ++ i) 
		ans += dis(A[i], A[i + 1]);  
	printf("%.2f", ans); 
	return 0; 
}

这篇关于计算几何模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！