computer geometry

point.cpp

class P
{
public:
  double x,y;
  P(){};P(double x,double y):x(x),y(y){};
  P &operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  P &operator-=(const P&q){x-=q.x;y-=q.y;return *this;}
  P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;}
  P operator-(const P&q){P t;t.x=x-q.x;t.y=y-q.y;return t;}
  template<typename T> P &operator*=(T d){x*=d;y*=d;return *this;}
  template<typename T> P &operator/=(T d){x/=d;y/=d;return *this;}
  template<typename T> P operator*(T d){return P(x*d,y*d);}
  template<typename T> P operator/(T d){return P(x/d,y/d);}
  bool operator<(const P&q)const{return (x!=q.x)?(x<q.x):(y<q.y);}
  bool operator>(const P&q)const{return (x!=q.x)?(x>q.x):(y>q.y);}
  double norm(void){return sqrt(x*x+y*y);}
  double arg(void){return acos(x/this->norm())*P(1,0).sign(*this);}
  P rotate(double t){double c=cos(t),s=sin(t);return P(c*x-s*y,s*x+c*y);}
  P nvec(void){return P(y,-x);}
  P reverseX(void){return P(-x,y);}
  P reverseY(void){return P(x,-y);}
  P unit(void){return (*this).norm()==0?P(0,0):(*this)/(*this).norm();}
  P floor(void){return P((int)x,(int)y);}
  double dot(const P&q){return x*q.x+y*q.y;}
  double det(const P&q){return x*q.y-y*q.x;}
  int sign(const P&q){double d = (*this).det(q); return (d>0)-(d<0);}
  static bool on_seg(P p1,P p2,P q){return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;}
  static P intersection(P p1,P p2,P q1,P q2){return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}
  static bool crossing(P p1,P p2,P q1,P q2)
  {
    if((p2-p1).sign(q2-q1)==0) return on_seg(p1,p2,q1)||on_seg(p1,p2,q2)||on_seg(q1,q2,p1)||on_seg(q1,q2,p2);
    double x=(q2-q1).det(q1-p1)/(q2-q1).det(p2-p1);
    double y=(p2-p1).det(p1-q1)/(p2-p1).det(q2-q1);
    return x<=1 && x>=0 && y<=1 && y>=0;
  }
};