# Geometry

Geometry template extension

```const double pi=M_PI;
#define area(a,b,c) ((b-a)^(c-a))
#define sqDist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y))
#define dist(a,b) sqrt(sqDist(a,b))
```

Geometric structures/classes used in my codes

```struct point{
#define DT int /// Datatype
DT x,y;
point():x(0),y(0){} /// default constructor
point(DT _x,DT _y):x(_x),y(_y){} /// constructor

bool operator < (point b) ; /// smaller than operator
bool operator == (point b) ; /// equal to operator
point operator - (point b) ; /// returns a vector from `this` to `b`
DT operator * (point b) ; /// Dot product of `this` and `b`
DT operator ^ (point b) ; /// Cross product of `this` and `b`
point pointBetween(point q,double m1,double m2);
/// returns a point from the joining segment of 'this' and 'q'
/// the distance ratio of which from 'this' and 'q' is m1:m2
};

bool point::operator < (point b) {
/// smaller than operator
if(!sgn(x,b.x)) return sgn(y,b.y)<0;
return sgn(x,b.x)<0;
}

bool point::operator == (point b) {
/// equal to operator
return !sgn(x,b.x) && !sgn(y,b.y);
}

point point::operator - (point b){
/// returns a vector from `this` to `b`
return point(x-b.x,y-b.y);
}

__typeof(point::x) point::operator * (point b){
/// Dot product
return x*b.x+y*b.y;
}

__typeof(point::x) point::operator ^ (point b){
/// Cross product
return x*b.y-y*b.x;
}

point point::pointBetween(point q,double m1,double m2){
/// returns a point from the joining segment of 'this' and 'q'
/// the distance ratio of which from 'this' and 'q' is m1:m2
return point( ( m1 * q.x + m2 * x ) / ( m1 + m2 ) , ( m1 * q.y + m2 * y ) / ( m1 + m2 ) );
}```
```struct line{
#define DT int /// Datatype
DT a,b,c;

line(){a=b=c=0;} /// default constructor
line(point p,point q):a(p.y-q.y),b(q.x-p.x),c(p.x*q.y-q.x*p.y){} /// constructor

bool operator < (line B); /// smaller than operator

void normalize(); /// generalizes the line coefficients 'a','b','c'
line perpendicular(point p);
/// returns the perpendicular line
/// which goes through point 'p'
};

void line::normalize(){
/// generalizes the line coefficients 'a','b','c'
__typeof(a) g=gcd(a,gcd(b,c));
a/=g, b/=g, c/=g;
int sign=(a<0 || (!a && b<0))?-1:1;
a*=sign, b*=sign, c*=sign;
}

line line::perpendicular(point p){
/// returns the perpendicular line
/// which goes through point 'p'
line ret;
ret.a=b, ret.b=-a;
ret.c=-p.x*ret.a-p.y*ret.b;
return ret;
}

bool line::operator < (line B) {
/// smaller than operator
if(!sgn(a,B.a)) {
return sgn(b,B.b)==0?sgn(c,B.c)<0:sgn(b,B.b)<0;
}
return sgn(a,B.a)<0;
}
```
```struct segment{
point A,B;
segment():A(point(0,0)),B(point(0,0)){}
segment(point _A,point _B):A(_A),B(_B){}
bool inside(point c); /// checks if a point is inside the enclosing rectangle
bool intersect(segment Q) ; /// checks if 'this' intersect with 'Q'
};

bool segment::inside(point c){
/// checks if a point is inside the enclosing rectangle
return (min(A.x,B.x)<=c.x && c.x<=max(A.x,B.x) && min(A.y,B.y)<=c.y && c.y<=max(A.y,B.y));
}

bool segment::intersect(segment Q){
/// checks if 'this' intersect with 'Q'
__typeof(A.x) d1=area(Q.A,Q.B,A);
__typeof(A.x) d2=area(Q.A,Q.B,B);
__typeof(A.x) d3=area(A,B,Q.A);
__typeof(A.x) d4=area(A,B,Q.B);
if( ((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))  ) return true;
if(!d1 && Q.inside(A)) return true;
if(!d2 && Q.inside(B)) return true;
if(!d3 && inside(Q.A)) return true;
if(!d4 && inside(Q.B)) return true;
return false;
}
```

Go Back