|
| 1 | +// Time: O(n^2 * logr), r = max(max(abs(x), abs(y)) for x, y in points) |
| 2 | +// Space: O(n^2) |
| 3 | + |
| 4 | +// math |
| 5 | +classSolution { |
| 6 | +private: |
| 7 | +structTupleHash { |
| 8 | +template<typename... T> |
| 9 | + std::size_toperator()(const std::tuple<T...>& t)const { |
| 10 | +returnapply([](constauto&... args) { |
| 11 | + std::size_t seed =0; |
| 12 | + ((seed ^= std::hash<std::decay_t<decltype(args)>>{}(args) + |
| 13 | +0x9e3779b9 + (seed <<6) + (seed >>2)), ...); |
| 14 | +return seed; |
| 15 | + }, t); |
| 16 | + } |
| 17 | + }; |
| 18 | + |
| 19 | +public: |
| 20 | +intcountTrapezoids(vector<vector<int>>& points) { |
| 21 | + unordered_map<tuple<int,int>,int, TupleHash> lookup_slope; |
| 22 | + unordered_map<tuple<int,int,int>,int, TupleHash> lookup_line; |
| 23 | + unordered_map<tuple<int,int,int>,int, TupleHash> lookup_slope_length; |
| 24 | + unordered_map<tuple<int,int,int,int>,int, TupleHash> lookup_line_length; |
| 25 | +int result =0, same =0; |
| 26 | +for (int i =0; i <size(points); ++i) { |
| 27 | +constint x1 = points[i][0], y1 = points[i][1]; |
| 28 | +for (int j =0; j < i; ++j) { |
| 29 | +constint x2 = points[j][0], y2 = points[j][1]; |
| 30 | +constint dx = x2 - x1, dy = y2 - y1; |
| 31 | +constauto& g =gcd(dx, dy); |
| 32 | +int a = dx / g, b = dy / g; |
| 33 | +if (a <0 || (a ==0 && b <0)) { |
| 34 | + a = -a; |
| 35 | + b = -b; |
| 36 | + } |
| 37 | +constint c = b * x1 - a * y1; |
| 38 | + result += lookup_slope[tuple(a, b)]++ - lookup_line[tuple(a, b, c)]++; |
| 39 | +constint l = dx * dx + dy * dy; |
| 40 | + same += lookup_slope_length[tuple(a, b, l)]++ - lookup_line_length[tuple(a, b, c, l)]++; |
| 41 | + } |
| 42 | + } |
| 43 | +return result - same /2; |
| 44 | + } |
| 45 | +}; |