Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct Dot
- {
- int x, y;
- Dot(int i, int j)
- {
- x = i;
- y = j;
- }
- bool operator==(const Dot& that)const
- {
- return x == that.x && y == that.y;
- }
- };
- struct Hasher
- {
- size_t operator()(const Dot& point)const
- {
- string str = to_string(point.x) + ":" + to_string(point.y);
- return hash<string>()(str);
- }
- };
- class Solution {
- public:
- double minAreaFreeRect(vector<vector<int>>& points) {
- int len = points.size();
- unordered_set<Dot, Hasher> set;
- for(auto& point : points)
- {
- Dot p(point[0], point[1]);
- set.insert(p);
- }
- double res = 40005 * 40005;
- for(int i = 0; i < len; ++i)
- {
- Dot p0(points[i][0], points[i][1]);
- for(int j = 0; j < len; ++j)
- {
- if(j == i)continue;
- Dot p1(points[j][0], points[j][1]);
- for(int k = j + 1; k < len; ++k)
- {
- if(k== i)continue;
- Dot p2(points[k][0], points[k][1]);
- Dot p3(p1.x + p2.x - p0.x, p1.y + p2.y - p0.y);
- if(set.find(p3) != set.end() && isPerpen(p0, p1, p2))
- {
- double e1 = getLen(p0, p1), e2 = getLen(p0, p2);
- res = min(res, e1 * e2);
- }
- }
- }
- }
- return res < 40005 * 40005? res : 0;
- }
- private:
- bool isPerpen(const Dot& p0, const Dot& p1, const Dot& p2)
- {
- Dot vector1(p1.x - p0.x, p1.y - p0.y), vector2(p2.x - p0.x, p2.y - p0.y);
- return vector1.x * vector2.x + vector1.y * vector2.y == 0;
- }
- double getLen(const Dot& p0, const Dot& p1)
- {
- return sqrt(pow(p1.x - p0.x, 2) + pow(p1.y - p0.y, 2));
- }
- };
Add Comment
Please, Sign In to add comment