Leetcode 149 Max Points on a Line(暴力+gcd)

タイトル接続:Leetcode 149 Max Points on a Line
解題構想:各点を基準点として列挙し、その後ろのすべての点と直線を行い、dy,dxで傾きを表す(傾きの表現方式が一致することを保証することに注意し、gcdと記号).mapでどれだけの傾きが同じ直線があるかを記録し、同じ点に注意します.

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
	public:
		int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }

		int maxPoints(vector& points) {
			map, int> g;
			int n = points.size(), ans = 0;

			for (int i = 0; i < n; i++) {
				int overlap = 0, tmp = 0;
				g.clear();

				for (int j = i + 1; j < n; j++) {
					int dy = points[j].y - points[i].y;
					int dx = points[j].x - points[i].x;

					if (dy == 0 && dx == 0) {
						overlap++;
						continue;
					}

					int d = gcd(dy, dx); dy /= d, dx /= d;

					if (dy < 0) dy *= -1, dx *= -1;

					pair k = make_pair(dy, dx);
					if (g.count(k)) g[k]++;
					else g[k] = 1;

					tmp = max(tmp, g[k]);
				}
				ans = max(ans, tmp + overlap + 1);
			}
			return ans;
		}
};