#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Point { public: int y, x; Point(){ y = x = 0; } Point(int y0, int x0){ y = y0; x = x0; } Point operator+(const Point& p) const{ return Point(y + p.y, x + p.x); } Point operator-(const Point& p) const{ return Point(y - p.y, x - p.x); } Point operator*(int a) const{ return Point(y * a, x * a); } bool operator==(const Point& p) const{ return y == p.y && x == p.x; } long long length2() const{ return y * (long long)y + x * (long long)x; } long long dist2(const Point& p) const{ return (y - p.y) * (long long)(y - p.y) + (x - p.x) * (long long)(x - p.x); } long long dot(const Point& p) const{ return y * (long long)p.y + x * (long long)p.x; // |a|*|b|*cosθ } long long cross(const Point& p) const{ return x * (long long)p.y - y * (long long)p.x; // |a|*|b|*sinθ } }; void solve(vector& s) { int h = s.size(); int w = s[0].size(); vector v; for(int y=0; y> h >> w; vector s(h); for(int i=0; i> s[i]; solve(s); for(int i=0; i