计算几何

计算几何

const double ZERO = 1e-10;

struct Point {
    double x, y;
    Point(int ts, int ty) {
    	x = ts;
    	y = ty;
	}
	Point(double ts,double ty) {
		x = ts;
		y = ty;
	}
	Point(){ x = y = 0; }
	double dist(Point a) {
		return sqrt((a.x-x)*(a.x-x) + (a.y-y)*(a.y-y));
	}
	bool operator == (const Point &that) const {
		return abs(x - that.x) < ZERO && abs(y - that.y) < ZERO;
	}
	
	bool operator < (const Point &that) const {
        if (abs(x - that.x) < ZERO) return y - that.y < ZERO;
        return x - that.x < ZERO;
    }

};

Point midpoint(Point a, Point b) {
	return Point((a.x+b.x)/2, (a.y+b.y)/2);
}

struct Vector {
    double x, y;
    
    Vector() { x = y = 0; }
    Vector(double tx, double ty) { x = tx; y = ty; }
	Vector(Point a, Point b) {
		x = b.x - a.x;
		y = b.y - a.y;
	} 

	Vector getsenkrecht() {
		return Vector(y, -x);
	}
	
	bool operator == (const Vector &that) const {
		return std::abs(x - that.x) < ZERO && std::abs(y - that.y) < ZERO;
	}

    double operator * (const Vector &that) {
        return x*that.x + y*that.y;
    }

	bool senkrecht(Vector that) {
		return std::abs(*this * that) < ZERO;
	}

    double abs() {
        return sqrt(x*x + y*y);
    }

    double operator ^ (const Vector &that) {
        return x*that.y - y*that.x;
    }
    
    double pankel(Vector that) {
	    Vector ts(x,y);
   		return acos(ts*that / (ts.abs()*that.abs()));
	}
    
    double ankel(Vector that) {
	    if ((*this ^ that ) < ZERO) return -acos((*this ^ that ) / (this->abs()*that.abs()));
   		return acos((*this ^ that ) / (this->abs()*that.abs()));
	}
	
	bool parallel(Vector that) {
		if(y*that.x*1.0 == x*that.y*1.0
		) return true;
		return false;
	}

	bool diffside(Vector that) {
		return x*that.x <= ZERO && y*that.y <= ZERO; 
	}

	bool anticlockwise(Vector that) {
		double ret =  (*this ^ that);
		if (std::abs(ret) < ZERO) return !(x*that.x <= ZERO && y*that.y <= ZERO);
		return ret > ZERO;
	}
};

struct Line {
    Point s;
    Vector v;
    
    Line(Point a, Point b) {
		s = a;
		v = Vector(a, b);
	}
	
	Line(Point ta, Vector tv) {
		s = ta;
		v = tv;
	}
	
	bool iscross(Line b) {
		if (v.parallel(b.v)) return false;
		return true;
	}
	
	double dist(Point a) {
		Vector vb(s, a);
		double ank = v.pankel(vb);
		return vb.abs()*sin(ank);
	}
	
	Point cross(Line b) {
		double x0 = s.x, y0 = s.y;
		double x0p = b.s.x, y0p = b.s.y;
		
		double xa = v.x, ya = v.y;
		double xb = b.v.x, yb = b.v.y;
		double _s;
		if (yb == 0) {
			_s = (y0p-y0)/ya;
			return Point(x0 + _s*xa, y0 + _s*ya);
		}
		_s = (x0-x0p + (y0p-y0)*xb/yb)/(ya*xb/yb - xa);
		return Point(x0 + _s*xa, y0 + _s*ya);
	}

	bool islie(Point a) {
		double _l = v.y*(a.x - s.x);
		double _r = v.x*(a.y - s.y);
		return std::abs(_l - _r) < ZERO;
	}
};

struct Segment {
	Point s;
	Vector v;
	Point st, ed;
	
	Segment() {s = st = ed = Point(); v = Vector(); }
	Segment(Point a, Point b) {
		s = st = a;
		ed = b;
		v = Vector(a, b);
	}
	
	bool iscross(Line b) {
		Line a(s,v);
		if (!a.iscross(b)) return false;
		Point c = a.cross(b);
		if (c == st || c == ed) return true;
		
		double k;
		if (b.v.x == 0) k = (c.y - b.s.y) / b.v.y;
		else k = (c.x - b.s.x) / b.v.x;
		if (k < 0) return false;
		
		double k1,k2;
		if (v.x == 0) {
		  	k1 = (c.y - st.y) / v.y;
		  	k2 = (c.y - ed.y) / v.y;
		} else {
			k1 = (c.x - st.x) / v.x;
			k2 = (c.x - ed.x) / v.x;
		}
	
		if (k1*k2 > 0) return false;
		else return true;
	}

	bool islie(Point a) {
		if (!Line(s, v).islie(a)) return false;
		if (a == ed || a == st) return true;
		if (Vector(a,st).diffside(Vector(a,ed))) return true;
		return false;
	}
};
bool segcross(Segment a, Segment b) {
	if (max(a.st.x,a.ed.x) < min(b.st.x, b.ed.x)) return false;
	if (max(a.st.y,a.ed.y) < min(b.st.y, b.ed.y)) return false;
	if (max(b.st.x,b.ed.x) < min(a.st.x, a.ed.x)) return false;
	if (max(b.st.y,b.ed.y) < min(a.st.y, a.ed.y)) return false;
	if ( (Vector(a.st, b.st) ^ b.v ) * (Vector(a.ed, b.st) ^ b.v) < ZERO &&
		 (Vector(b.st, a.st) ^ a.v ) * (Vector(b.ed, a.st) ^ a.v) < ZERO   ) return true;
	return false;
}