Orz发现之前的版子有小错误都不知道怎么在用2333
8.8更新多边形计算+求直线交点 顺便把之前版子统一了一下 希望这周解决计算几何 然后就不用再看模板了
忘记加重载 / 了。。 更了另一个求交点情况，不会有除0情况出现
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100; const double eps = 1e-6; int sgn(double x) { return x<-eps?-1:x>eps?1:0;} double sqr(double x) { return x*x;} double mysqrt(double n) { return sqrt(max(0.0,n));} struct point { double x,y; point(double _x=0,double _y=0) { x = _x; y = _y; } }; typedef point Vector; //向量-向量 Vector operator -(const Vector &a, const Vector &b) {return Vector(a.x-b.x, a.y-b.y);} //向量+向量 Vector operator +(const Vector &a, const Vector &b) {return Vector(a.x+b.x, a.y+b.y);} //向量*常数 Vector operator *(const double &a, const Vector &b) {return Vector(a*b.x, a*b.y);} Vector operator *(const Vector &a, const double &b) {return Vector(a.x*b, a.y*b);} Vector operator /(const Vector &a, const double &b) {return Vector(a.x/b,a.y/b);} //向量*向量 Dot double dot(const Vector &a,const Vector &b) {return a.x*b.x+a.y*b.y;} //向量X向量 double cross(const Vector &a,const Vector &b) {return a.x*b.y-a.y*b.x;} //向量==向量 bool isequal(const Vector &a,const Vector &b) {return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;} double Length(Vector a) {return sqrt(dot(a,a));} //AB夹角 double Angle(Vector a,Vector b) {return acos( dot(a,b)/Length(a)/Length(b) );} //AB、AC组成的平行四边形面积 double Area(point a,point b,point c) {return cross((b-a),(c-a));} //A逆时针旋转弧度rad后的向量 Vector Rotate(Vector a,double rad) {return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));} //计算A的单位法线，保证A不为0向量 Vector Normal(Vector a) { double L = Length(a); return Vector(-a.y/L,a.x/L); } struct line { point s,e; line(){} line(point _s,point _e) { s = _s; e = _e; } }; //线段是否相交、端点算相交 bool inter(line l1,line l2) { return min(l1.s.x,l1.e.x)<=max(l2.s.x,l2.e.x) && min(l2.s.x,l2.e.x)<=max(l1.s.x,l1.e.x) && min(l1.s.y,l1.e.y)<=max(l2.s.y,l2.e.y) && min(l2.s.y,l2.e.y)<=max(l1.s.y,l1.e.y) && sgn(cross((l2.s-l1.e),(l1.s-l1.e))) * sgn(cross((l2.e-l1.e),(l1.s-l1.e)))<=0 && sgn(cross((l1.s-l2.e),(l2.s-l2.e))) * sgn(cross((l1.e-l2.e),(l2.s-l2.e)))<=0; } //线段是否相交、端点不算相交 bool inter2(line l1,line l2) { point a1=l1.s,a2=l1.e; point b1=l2.s,b2=l2.e; double c1 = cross((a2-a1),(b1-a1)), c2 = cross((a2-a1),(b2-a1)); double c3 = cross((b2-b1),(a1-b1)), c4 = cross((b2-b1),(a2-b1)); return sgn(c1)*sgn(c2)<0 && sgn(c3)*sgn(c4)<0; } //求n边形的面积、res[0~n-1]顺序存顶点、n为顶点数,res[n]=res[0] double area(point res[],int n) { double ret = 0; res[n] = res[0]; for(int i=0;i<n;i++) { ret += cross(res[i],res[i+1]); } return fabs(ret/2); } //求两线交点，要先判断有无交点 point GetLineInterPoint(line l1,line l2) { Vector v = l1.e-l1.s; Vector w = l2.e-l2.s; Vector u = l1.s-l2.s; double t = cross(w,u)/cross(v,w); return l1.s+v*t; } //求ab与pq交点，功能同上个函数一样 point crosspt(const point &a, const point &b, const point &p, const point &q) { double a1 = cross(b-a,p-a); double a2 = cross(b-a,q-a); return (p*a2-q*a1)/(a2-a1); }