《Cracking the Coding Interview》——第7章:数学と確率論——テーマ6
21552 ワード
2014-03-20 02:24
テーマ:2つの平面上の点の山を与えて、1本の直線を見つけて、それを通る点の数が最も多いです.
解法:私の解法は整点しか適用できません.実数座標については効率の低い方法に変えなければなりません.LeetCode-Max Points on a Line-zhuli 19901106-ブログ園を参照してください.
コード:
テーマ:2つの平面上の点の山を与えて、1本の直線を見つけて、それを通る点の数が最も多いです.
解法:私の解法は整点しか適用できません.実数座標については効率の低い方法に変えなければなりません.LeetCode-Max Points on a Line-zhuli 19901106-ブログ園を参照してください.
コード:
1 // 7.6 Find the line that crosses the most points.
2 #include <unordered_map>
3 #include <vector>
4 using namespace std;
5
6 struct Point {
7 int x;
8 int y;
9 Point() : x(0), y(0) {}
10 Point(int a, int b) : x(a), y(b) {}
11 };
12
13 struct st {
14 int x;
15 int y;
16 st(int _x = 0, int _y = 0): x(_x), y(_y) {};
17
18 bool operator == (const st &other) const {
19 return x == other.x && y == other.y;
20 };
21
22 bool operator != (const st &other) const {
23 return x != other.x || y != other.y;
24 };
25 };
26
27 struct line {
28 // ax + by + c = 0;
29 int a;
30 int b;
31 int c;
32 line(int _a = 0, int _b = 0, int _c = 0): a(_a), b(_b), c(_c) {};
33 };
34
35 struct hash_functor {
36 size_t operator () (const st &a) const {
37 return (a.x * 1009 + a.y);
38 }
39 };
40
41 struct compare_functor {
42 bool operator () (const st &a, const st &b) const {
43 return (a.x == b.x && a.y == b.y);
44 }
45 };
46
47 typedef unordered_map<st, int, hash_functor, compare_functor> st_map;
48
49 class Solution {
50 public:
51 int maxPoints(vector<Point> &points, line &result_line) {
52 int n = (int)points.size();
53
54 if (n <= 2) {
55 return n;
56 }
57
58 st_map um;
59 st tmp;
60 // special tangent value for duplicate points
61 st dup(0, 0);
62
63 int i, j;
64 st_map::const_iterator umit;
65 int dup_count;
66 int max_count;
67 int result = 0;
68 for (i = 0; i < n; ++i) {
69 for (j = i + 1; j < n; ++j) {
70 tmp.x = points[j].x - points[i].x;
71 tmp.y = points[j].y - points[i].y;
72 // make sure one tangent value has one representation only.
73 normalize(tmp);
74 if (um.find(tmp) != um.end()) {
75 ++um[tmp];
76 } else {
77 um[tmp] = 1;
78 }
79 }
80 max_count = dup_count = 0;
81 for (umit = um.begin(); umit != um.end(); ++umit) {
82 if (umit->first != dup) {
83 if (umit->second > max_count) {
84 max_count = umit->second;
85 getLine(umit->first, points[i], result_line);
86 }
87 } else {
88 dup_count = umit->second;
89 }
90 }
91 max_count = max_count + dup_count + 1;
92 result = (max_count > result ? max_count : result);
93 um.clear();
94 }
95
96 return result;
97 }
98 private:
99 void normalize(st &tmp) {
100 if (tmp.x == 0 && tmp.y == 0) {
101 // (0, 0)
102 return;
103 }
104 if (tmp.x == 0) {
105 // (0, 1)
106 tmp.y = 1;
107 return;
108 }
109 if (tmp.y == 0) {
110 // (1, 0)
111 tmp.x = 1;
112 return;
113 }
114 if (tmp.x < 0) {
115 // (-2, 3) and (2, -3) => (2, -3)
116 tmp.x = -tmp.x;
117 tmp.y = -tmp.y;
118 }
119
120 int gcd_value;
121
122 gcd_value = (tmp.y > 0 ? gcd(tmp.x, tmp.y) : gcd(tmp.x, -tmp.y));
123 // (4, -6) and (-30, 45) => (2, -3)
124 // using a double precision risks in accuracy
125 // so I did it with a pair
126 tmp.x /= gcd_value;
127 tmp.y /= gcd_value;
128 }
129
130 int gcd(int x, int y) {
131 // used for reduction of fraction
132 return y ? gcd(y, x % y) : x;
133 }
134
135 void getLine(st tan, Point p, line &res) {
136 res.a = tan.y;
137 res.b = -tan.x;
138 res.c = -(res.a * p.x + res.b * p.y);
139 }
140 };
141
142 int main()
143 {
144 vector<Point> v;
145 Solution sol;
146 int i, n;
147 Point p;
148 line res;
149
150 while (scanf("%d", &n) == 1) {
151 for (i = 0; i < n; ++i) {
152 scanf("%d%d", &p.x, &p.y);
153 v.push_back(p);
154 }
155 sol.maxPoints(v, res);
156 printf("%d %d %d
", res.a, res.b, res.c);
157 v.clear();
158 }
159
160 return 0;
161 }