我的计算几何模板,更新中

下面的代码中, P是点类,S是线段或直线类,A是多边形类.

#include <cstdio>
#include <cstring>
#include <stack>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define rep(i,n)  for (int i = 0; i < (n); i++)
#define per(i,n)  for (int i = (n); i>=0;i--)
#define mset(s,i) memset(s,i,sizeof(s))

double EPS = 1e-10;

double add(double a,double b) { return fabs(a+b)<EPS*(fabs(a)+fabs(b)) ? 0 : a+b; }

struct P {
	double x,y;
	P(double x=0.0,double y=0.0) : 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 operator() (P p) { return add(x*p.x,y*p.y); }  //点乘 
	double operator[] (P p) { return add(x*p.y,-y*p.x); } //叉乘 
};

struct S {
	P a,b;
	S() {}
	S(P a,P b) : a(a),b(b) {}
	double operator[] (P p) { return (a-p)[b-p]; }  //pa与pb的外积 
	bool operator&&(P p) { return (*this)[p]==0 && (p-a)(p-b) <=0; }    //p 在线段ab上
	P operator^(S s) {                              //两线段所在直线的交点 
		double d= (s.b-s.a)[s.a-a] / (s.b-s.a)[b-a];
		return a+(b-a)*d;
	}
	bool operator||(S s) { return (a-b)[s.a-s.b] == 0; }
};

typedef vector<P> A;

bool cmp_x(const P &p,const P &q) { return (p.x!=q.x)? (p.x<q.x) : (p.y<q.y); }

A convex(A ps) {
	int n=ps.size(),k=0;
	sort(ps.begin(),ps.end(),cmp_x);
	A qs(n*2);
	rep(i,n) {
		while(k>1 && (qs[k-1]-qs[k-2])[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])[ps[i]-qs[k-1]] <=0) k--;
		qs[k++] = ps[i];
	}
	qs.resize(k-1);
	return qs;	
}

double area(A &p) {
	int n=p.size(),j;
	double res=0;
	for(int i=0;i<n;i++) {
		j=(i+1)%n;
		res += p[i][p[j]];
	}
	return res/2.0;
}#include <cstdi