Math Vector Template
Haven't yet tested well, might have some bugs.
#include <bits/stdc++.h> using namespace std; const double EPS = 1e-10; const double PI = acos( -1.0 ); int dcmp(double x){ if( fabs( x ) < EPS ) return 0; return x < 0 ? -1 : 1; } struct Vector{ double x, y; Vector(double _x = 0, double _y = 0):x(_x),y(_y){} friend Vector operator + (Vector A, Vector B){ return Vector( A.x + B.x, A.y + B.y ); } friend Vector operator - (Vector A, Vector B){ return Vector( A.x - B.x, A.y - B.y ); } friend Vector operator * (Vector A, double p){ return Vector( A.x * p, A.y * p ); } friend Vector operator / (Vector A, double p){ return Vector( A.x / p, A.y / p ); } friend bool operator < (const Vector &A, const Vector &B){ return A.x < B.x || ( A.x == B.x && A.y < B.y ); } friend bool operator == (const Vector &A, const Vector &B){ return A.x == B.x && A.y == B.y; } friend bool operator <= (const Vector &A, const Vector &B){ return A < B || A == B; } friend bool operator > (const Vector &A, const Vector &B){ return !( A <= B ); } friend bool operator >= (const Vector &A, const Vector &B){ return !( A < B ); } friend double Dot(Vector A, Vector B){ return A.x * B.x + A.y * B.y; } friend double Length(Vector A){ return sqrt( Dot( A, A ) ); } friend double Angle(Vector A, Vector B){ return acos( Dot( A, B ) / Length( A ) / Length( B ) ); } friend double Cross(Vector A, Vector B){ return A.x * B.y - A.y * B.x; } friend double Area2(Vector A, Vector B, Vector C){ return Cross( B - A, C - A ); } friend Vector Rotate(Vector A, double rad){ return Vector( A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad) ); } friend Vector Normal(Vector A){ double L = Length( A ); return Vector( -A.y / L, A.x / L ); } friend Vector GetLineIntersection(Vector P, Vector v, Vector Q, Vector w){ Vector u = P - Q; // P + tv, Q + tw, intersection, make sure there is one before calling! double t = Cross( w, u ) / Cross( v, w ); // make sure Cross( v, w ) != 0, -> not parallel return P + v * t; } friend double DistanceToLine(Vector P, Vector A, Vector B){ Vector v1 = B - A, v2 = P - A; // returns distance perpendicular to line AB return fabs( Cross( v1, v2 ) ) / Length( v1 ); } friend double DistanceToSegment(Vector P, Vector A, Vector B){ // returns distance from p to segment AB if( A == B ) return Length( P - A ); Vector v1 = B - A, v2 = P - A, v3 = P - B; if( dcmp( Dot( v1, v2 ) ) < 0 ) return Length( v2 ); else if( dcmp( Dot( v1, v3 ) > 0 ) ) return Length( v3 ); return fabs( Cross( v1, v2 ) ) / Length( v1 ); } friend Vector GetLineProjection(Vector P, Vector A, Vector B){ Vector v = B - A; return A + v * ( Dot( v, P - A ) / Dot( v, v ) ); } friend bool SegmentProperIntersection(Vector a1, Vector a2, Vector b1, Vector b2){ double c1 = Cross( a2 - a1, b1 - a1 ), c2 = Cross( a2 - a1, b2 - a1 ), c3 = Cross( b2 - b1, a1 - b1 ), c4 = Cross( b2 - b1, a2 - b1 ); return dcmp( c1 ) * dcmp( c2 ) < 0 && dcmp( c3 ) * dcmp( c4 ) < 0; } friend double PolygonArea(vector<Vector> p){ double area = 0; int n = p.size(); for(int i = 1; i < n - 1; ++i) area += Cross( p[i] - p[0], p[i + 1] - p[0] ); return area / 2; // might be - signed, haven't tried yet } friend bool isPointOnSegment(Vector p, Vector a1, Vector a2){ return dcmp( Cross( a1 - p, a2 - p ) == 0 && dcmp( Dot( a1 - p, a2 - p ) ) < 0 ); } friend int isPointInPolygon(Vector p, vector<Vector> poly){ int wn = 0; int n = poly.size(); for(int i = 0; i < n; ++i){ if( isPointOnSegment( p, poly[i], poly[(i + 1) % n] ) ) return -1; // on border int k = dcmp( Cross( poly[(i + 1) % n] - poly[i], p - poly[i] ) ); int d1 = dcmp( poly[i].y - p.y ); int d2 = dcmp( poly[(i + 1) % n].y - p.y ); if( k > 0 && d1 <= 0 && d2 > 0 ) ++wn; if( k < 0 && d2 <= 0 && d1 > 0 ) --wn; } if( wn != 0 ) return 1; return 0; } friend vector<Vector> ConvexHull(vector<Vector> p){ sort( p.begin(), p.end() ); p.erase( unique( p.begin(), p.end() ), p.end() ); int m = 0; int n = p.size(); vector<Vector> ch( n + 1 ); for(int i = 0; i < n; ++i){ while( m > 1 && Cross( ch[m - 1] - ch[m - 2], p[i] - ch[m - 2] ) <= 0 ) --m; ch[ m++ ] = p[i]; } int k = m; for(int i = n - 2; i >= 0; --i){ while( m > k && Cross( ch[m - 1] - ch[m - 2], p[i] - ch[m - 2] ) <= 0 ) --m; ch[ m++ ] = p[i]; } if( n > 1 ) --m; ch.resize( m ); return ch; } }; int main(){ return 0; }