» » Miscellaneous Geometry

Miscellaneous Geometry

   7:44 PM       

 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define mx 100
#define pii pair < int, int >
#define i64 long long
#define eps 1e-9
#define _min(i,j) ((i)>(j+eps)?(j):(i))
#define _max(i,j) ((i)>(j+eps)?(i):(j))

struct point{
	i64 x,y;
	point(){}
	point(i64 xx, i64 yy){x = xx;y = yy;}
};

struct line { // Creates a line with equation ax + by + c = 0
	i64 a, b, c;
	line() {}
	line( point p1,point p2 ) {
		a=p1.y-p2.y;
		b=p2.x-p1.x;
		c=p1.x*p2.y-p2.x*p1.y;
	}
};

struct segment{
	point st,end;
	segment(){}
	segment(point a,point b){st = a;end = b;}
};

struct rect{
	point ul,lr;
	rect(){}
	rect(point a, point b){ul = a;lr = b;}
};

struct tr{
	point p[3];
	tr(){}
	tr(point a, point b, point c){p[0] = a; p[1] = b; p[2] = c;}
};

struct circle{
	i64 r;
	point center;
	circle(){}
	circle(point b,i64 a){r = a; center = b;}
};

struct polygon {
	int n;
	point P[mx];
};

inline bool feq(i64 a, i64 b){
	return (fabs(a-b)<eps);
}
inline i64 dist(point a, point b){
	return ( (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y) );
}
inline i64 isLeft(point a, point b, point c){
	return ( (a.x*b.y) + (b.x*c.y) + (c.x*a.y) - (a.y*b.x) - (b.y*c.x) - (c.y*a.x) );
}
inline bool onSegment(point a,point b,point c){
	if( (_min(a.x,b.x) < c.x || feq(_min(a.x,b.x),c.x)) && (c.x < _max(a.x,b.x) || feq(c.x,_max(a.x,b.x))) )
		if( (_min(a.y,b.y) < c.y || feq(_min(a.y,b.y),c.y) ) && (c.y < _max(a.y,b.y) || feq(c.y,_max(a.y,b.y))) )return true;
	return false;
}
inline bool isSegIntersect(point p1,point p2,point p3,point p4){
	i64 d1,d2,d3,d4;
	d1 = isLeft(p1,p2,p3);
	d2 = isLeft(p1,p2,p4);
	d3 = isLeft(p3,p4,p1);
	d4 = isLeft(p3,p4,p2);
	if( (d1*d2)<0 && (d3*d4)<0 )return true;
	else if(feq(d1,(i64)0) && onSegment(p1,p2,p3))return true;
	else if(feq(d2,(i64)0) && onSegment(p1,p2,p4))return true;
	else if(feq(d3,(i64)0) && onSegment(p3,p4,p1))return true;
	else if(feq(d4,(i64)0) && onSegment(p3,p4,p2))return true;
	return false;
}

inline bool intersection( line L1, line L2, point &p ) {// If two line intersect each other
	i64 det = L1.a * L2.b - L1.b * L2.a;
	if( feq(det,(i64)0) ) return false;
	p.x = ( L1.b * L2.c - L2.b * L1.c ) / det;
	p.y = ( L1.c * L2.a - L2.c * L1.a ) / det;
	return true;
}

inline bool inRect(rect r, point p){// If a point inside a rectangle
	if( (p.x > r.ul.x && p.x < r.lr.x) && (p.y < r.ul.y && p.y > r.lr.y) ) return true;
	return false;
}

inline bool inTr(tr t, point p){// If a point inside a triangle
	i64 d,d1,d2,d3;
	d = fabs( isLeft(t.p[0],t.p[1],t.p[2]) );
	d1 = fabs( isLeft(t.p[0],t.p[1],p) );
	if( feq(d1,(i64)0) && onSegment(t.p[0],t.p[1],p) )return false;
	d2 = fabs( isLeft(t.p[1],t.p[2],p) );
	if( feq(d2,(i64)0) && onSegment(t.p[1],t.p[2],p) )return false;
	d3 = fabs( isLeft(t.p[2],t.p[0],p) );
	if( feq(d3(i64)0) && onSegment(t.p[2],t.p[0],p) )return false;
	return feq(d,d1+d2+d3);
}

inline bool inCircle(circle c,point p){// If a point inside a circle
	if( dist(c.center,p)+eps < c.r ) return true;
	return false;
}