1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cmath>
#include <complex>
#include <valarray>
#include <functional>

// not seperate *.h and *.cpp
// for convenience in contest

template<class T>
class GeoVec {
    public:
        T x, y;
        GeoVec() {}
        GeoVec(const T &x, const T &y) : x(x), y(y) {}
        GeoVec(const GeoVec &copy) : x(copy.x), y(copy.y) {}
        const GeoVec operator*(T a) const { return GeoVec(x*a,y*a); }
        const GeoVec operator/(T a) const { return GeoVec(x/a,y/a); }
        static const T L1(const GeoVec &a) {
            return std::sqrt(a.x*a.x + a.y*a.y);
        }
        static const T L2(const GeoVec &a) {
            return (a.x*a.x + a.y*a.y);
        }
        const GeoVec rot(T rad) const {
            using std::cos;
            using std::sin;
            return GeoVec(cos(rad)*x-sin(rad)*y, sin(rad)*x+cos(rad)*y);
        }
        const GeoVec unitVec(void) const { return (*this/(L1(*this))); }
        const GeoVec tVec(void) const { return GeoVec(-y, x); }
        const T cross(const GeoVec &v) {
            return (this->x*v.y - this->y*v.x);
        }
        // 點向式
        // 從 Line: sx,sy 射出的向量 v , dot: x, y
        double dot2Line(T x, T y, T sx, T sy, const GeoVec &v) {
            GeoVec u(x-sx, y-sy);
            // 向量 sx, sy 射出的向量到 x, y
            T cross = v.cross(u);
            // v x u 得到面積
            if(cross<0) cross=-cross;
            return cross/L1(v);
            // 面積 / 底 = 高（點到直線距離）
        }
        // 求 a1xb1y+c1=0, a2xb2y+c2=0 交點
        static GeoVec twoLineSec(T a1, T b1, T c1, T a2, T b2, T c2) {
            // 小心除 0
            return GeoVec((c1*a2-a1*c2) / (b1*a2-b2*a1),
                          (c1*b2-c2*b1) / (a1*b2-b1*a1));
        }
};
// all public for convenient in contest
// following are operator overloading for class template GeoVec
template<class T>
const GeoVec<T> operator+(const GeoVec<T> &first, const GeoVec<T> &second) {
    return GeoVec<T>(first.x+second.x, first.y+second.y);
}

template<class T>
const GeoVec<T> operator-(const GeoVec<T> &first, const GeoVec<T> &second) {
    return GeoVec<T>(first.x-second.x, first.y-second.y);
}

template<class T>
const T operator*(const GeoVec<T> &first, const GeoVec<T> &second) {
    // dot product
    return (first.x*second.x + first.y*second.y);
}

template<class T>
const T operator%(const GeoVec<T> &first, const GeoVec<T> &second) {
    // cross product
    return first.cross(second);
}