回答編集履歴
5
edit
test
CHANGED
@@ -16,9 +16,9 @@
|
|
16
16
|
|
17
17
|
for _ in range(3):
|
18
18
|
|
19
|
-
mcnt =
|
19
|
+
mcnt = -1
|
20
20
|
|
21
|
-
best =
|
21
|
+
best = -1
|
22
22
|
|
23
23
|
mcovered = None
|
24
24
|
|
@@ -82,7 +82,7 @@
|
|
82
82
|
|
83
83
|
mcnt = -1
|
84
84
|
|
85
|
-
best =
|
85
|
+
best = -1
|
86
86
|
|
87
87
|
mcovered = []
|
88
88
|
|
4
edit
test
CHANGED
@@ -6,9 +6,9 @@
|
|
6
6
|
|
7
7
|
np.random.seed(2018)
|
8
8
|
|
9
|
-
points = np.random.random((100, 2))*
|
9
|
+
points = np.random.random((1000, 2))*10
|
10
10
|
|
11
|
-
base_points = np.random.random((10, 2))*
|
11
|
+
base_points = np.random.random((1000, 2))*10
|
12
12
|
|
13
13
|
|
14
14
|
|
@@ -42,15 +42,25 @@
|
|
42
42
|
|
43
43
|
points = points[np.logical_not(mcovered)]
|
44
44
|
|
45
|
+
print(best)
|
46
|
+
|
47
|
+
print(mcnt)
|
48
|
+
|
49
|
+
print(points.shape)
|
50
|
+
|
45
51
|
|
46
52
|
|
47
53
|
centers = np.array(centers)
|
48
54
|
|
49
55
|
import matplotlib.pyplot as plt
|
50
56
|
|
51
|
-
plt.s
|
57
|
+
fig, ax = plt.subplots(dpi=200)
|
52
58
|
|
59
|
+
ax.set_aspect('equal')
|
60
|
+
|
61
|
+
ax.scatter(points[:, 0], points[:, 1], s=10)
|
62
|
+
|
53
|
-
|
63
|
+
ax.scatter(centers[:, 0], centers[:, 1], c='red', s=15**2)
|
54
64
|
|
55
65
|
plt.show()
|
56
66
|
|
3
edit
test
CHANGED
@@ -1,3 +1,73 @@
|
|
1
|
+
```python
|
2
|
+
|
3
|
+
import numpy as np
|
4
|
+
|
5
|
+
|
6
|
+
|
7
|
+
np.random.seed(2018)
|
8
|
+
|
9
|
+
points = np.random.random((100, 2))*2
|
10
|
+
|
11
|
+
base_points = np.random.random((10, 2))*2
|
12
|
+
|
13
|
+
|
14
|
+
|
15
|
+
centers = []
|
16
|
+
|
17
|
+
for _ in range(3):
|
18
|
+
|
19
|
+
mcnt = 0
|
20
|
+
|
21
|
+
best = 0
|
22
|
+
|
23
|
+
mcovered = None
|
24
|
+
|
25
|
+
for i, bp in enumerate(base_points):
|
26
|
+
|
27
|
+
dist = np.linalg.norm(points - bp, axis=-1)
|
28
|
+
|
29
|
+
covered = dist < 0.5
|
30
|
+
|
31
|
+
cnt = np.sum(covered)
|
32
|
+
|
33
|
+
if cnt > mcnt:
|
34
|
+
|
35
|
+
mcovered = covered
|
36
|
+
|
37
|
+
mcnt = cnt
|
38
|
+
|
39
|
+
best = i
|
40
|
+
|
41
|
+
centers.append(base_points[best])
|
42
|
+
|
43
|
+
points = points[np.logical_not(mcovered)]
|
44
|
+
|
45
|
+
|
46
|
+
|
47
|
+
centers = np.array(centers)
|
48
|
+
|
49
|
+
import matplotlib.pyplot as plt
|
50
|
+
|
51
|
+
plt.scatter(points[:, 0], points[:, 1])
|
52
|
+
|
53
|
+
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=10**3)
|
54
|
+
|
55
|
+
plt.show()
|
56
|
+
|
57
|
+
```
|
58
|
+
|
59
|
+
|
60
|
+
|
61
|
+
一般的にpythonは遅くて、高速化するためには外部ライブラリを使用して一気に処理します。
|
62
|
+
|
63
|
+
今の場合、点の集合から置局までの距離を一気に計算することができます。
|
64
|
+
|
65
|
+
|
66
|
+
|
67
|
+
---
|
68
|
+
|
69
|
+
|
70
|
+
|
1
71
|
```python
|
2
72
|
|
3
73
|
mcnt = -1
|
2
edit
test
CHANGED
@@ -4,9 +4,13 @@
|
|
4
4
|
|
5
5
|
best = 0
|
6
6
|
|
7
|
+
mcovered = []
|
8
|
+
|
7
9
|
for i in range(len(base_points)):
|
8
10
|
|
9
11
|
cnt = 0
|
12
|
+
|
13
|
+
covered = []
|
10
14
|
|
11
15
|
for j in range(len(points)):
|
12
16
|
|
@@ -16,11 +20,17 @@
|
|
16
20
|
|
17
21
|
cnt = cnt + 1
|
18
22
|
|
23
|
+
covered.append(j)
|
24
|
+
|
19
25
|
if cnt > mcnt:
|
20
26
|
|
21
27
|
mcnt = cnt
|
22
28
|
|
23
29
|
best = i
|
30
|
+
|
31
|
+
mcovered = covered
|
32
|
+
|
33
|
+
points = list(set(points) - set(mcovered))
|
24
34
|
|
25
35
|
```
|
26
36
|
|
@@ -30,7 +40,9 @@
|
|
30
40
|
|
31
41
|
|
32
42
|
|
33
|
-
取り除くのはpopでも使えばよいでしょう。
|
43
|
+
~~取り除くのはpopでも使えばよいでしょう。~~
|
44
|
+
|
45
|
+
setの引き算にしました。
|
34
46
|
|
35
47
|
|
36
48
|
|
1
edit
test
CHANGED
@@ -42,24 +42,6 @@
|
|
42
42
|
|
43
43
|
|
44
44
|
|
45
|
-
再度計算する際に置局のカバーする点の数が変わらないことに気づけば、カバーできる点の個数を配列にして、それをソートすることでより高速に解を求めることができます。
|
46
|
-
|
47
|
-
|
48
|
-
|
49
|
-
使うものはsorted, itemgetter, zipあたりでしょう。
|
50
|
-
|
51
|
-
http://please-sleep.cou929.nu/python-sorted-function-interface.html
|
52
|
-
|
53
|
-
|
54
|
-
|
55
|
-
さらにはやくするのなら、numpyを使って、sortargsを使います。
|
56
|
-
|
57
|
-
|
58
|
-
|
59
|
-
---
|
60
|
-
|
61
|
-
|
62
|
-
|
63
45
|
余談ですが、CAL_RHOの設計が悪いです。
|
64
46
|
|
65
47
|
2点間の距離を計算する関数ですから、x1,x2,y1,y2を引数にすると順番をミスると大変なことになります。
|