質問編集履歴
2
プログラムの追加
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -13,6 +13,240 @@
|
|
|
13
13
|
|
|
14
14
|
```c++
|
|
15
15
|
|
|
16
|
+
#define MAX_NUMBER 1000
|
|
17
|
+
#define FLAG_OFF 0
|
|
18
|
+
#define FLAG_ON 1
|
|
19
|
+
#define EPS 0.000001
|
|
20
|
+
#define V_NO_ERROR 0
|
|
21
|
+
#define V_ERROR 1
|
|
22
|
+
|
|
23
|
+
typedef struct {
|
|
24
|
+
double x, y;
|
|
25
|
+
int flag;
|
|
26
|
+
}POINT;
|
|
27
|
+
|
|
28
|
+
POINT p[MAX_NUMBER];
|
|
29
|
+
int number_of_points;
|
|
30
|
+
|
|
31
|
+
int find_point_with_minimum_x(void);
|
|
32
|
+
|
|
33
|
+
void make_2d_convex_hull(void);
|
|
34
|
+
void take_coordinate_of_point(int point_number, double v[]);
|
|
35
|
+
void determine_direction_of_base_line(double uv[], int point1, int point2);
|
|
36
|
+
void sort_using_distance(int ct[], int n, int p);
|
|
37
|
+
void vsub_(double v[], double v1[], double v2[], int *n);
|
|
38
|
+
void vunit_(double v[], double v0[], int *n, int *ierror);
|
|
39
|
+
double vinpro_(double v1[], double v2[], int *n);
|
|
40
|
+
|
|
41
|
+
int main(void)
|
|
42
|
+
{
|
|
43
|
+
FILE *fp;
|
|
44
|
+
int i = 0;
|
|
45
|
+
int point_number;
|
|
46
|
+
int n = 2;
|
|
47
|
+
double v1[2], v2[2], v[2];
|
|
48
|
+
double d;
|
|
49
|
+
errno_t err;
|
|
50
|
+
|
|
51
|
+
/*点データの入力*/
|
|
52
|
+
if ((err = fopen_s(&fp,"point_table.dat.txt", "r")) == '0') {
|
|
53
|
+
printf("cannot open point_table.dat\n");
|
|
54
|
+
return 0;
|
|
55
|
+
}
|
|
56
|
+
while (fscanf_s(fp, "%lf%lf", &p[i].x, &p[i].y) != EOF) {
|
|
57
|
+
p[i].flag = FLAG_OFF;
|
|
58
|
+
i++;
|
|
59
|
+
}
|
|
60
|
+
fclose(fp);
|
|
61
|
+
/*点の数の設定*/
|
|
62
|
+
number_of_points = i;
|
|
63
|
+
|
|
64
|
+
/*点データの出力*/
|
|
65
|
+
for (i = 0; i < number_of_points; i++) {
|
|
66
|
+
printf("%3d %7.3lf %7.3lf %d\n", i, p[i].x, p[i].y, p[i].flag);
|
|
67
|
+
}
|
|
68
|
+
/*２次元コンベックスハルの生成*/
|
|
69
|
+
make_2d_convex_hull();
|
|
70
|
+
|
|
71
|
+
return 0;
|
|
72
|
+
}
|
|
73
|
+
|
|
74
|
+
void make_2d_convex_hull(void)
|
|
75
|
+
{
|
|
76
|
+
int start_point;
|
|
77
|
+
int convex_point;
|
|
78
|
+
int number_of_convex_points = 0;
|
|
79
|
+
int cp[MAX_NUMBER];/*凸多角形を構成する点の並び*/
|
|
80
|
+
int ctemp[10];
|
|
81
|
+
int count;
|
|
82
|
+
int n = 2;
|
|
83
|
+
int ierror;
|
|
84
|
+
int i, k;
|
|
85
|
+
double v0[2], v1[2], v2[2], v[2], uv[2];
|
|
86
|
+
double d, dmax;
|
|
87
|
+
|
|
88
|
+
/*座標が最小の点を求める*/
|
|
89
|
+
convex_point = find_point_with_minimum_x();
|
|
90
|
+
printf("凸多角形を構成する１番目の点：%d\n", convex_point);
|
|
91
|
+
start_point = convex_point;
|
|
92
|
+
cp[number_of_convex_points] = convex_point;
|
|
93
|
+
number_of_convex_points++;
|
|
94
|
+
|
|
95
|
+
/*基準線の方向を設定する（ｙ軸の負の方向）*/
|
|
96
|
+
uv[0] = 0.0; uv[1] = -1.0;
|
|
97
|
+
/*凸多角形を構成する２番目以降の点を求める*/
|
|
98
|
+
while (1) {
|
|
99
|
+
take_coordinate_of_point(convex_point, v1);
|
|
100
|
+
k = convex_point;
|
|
101
|
+
dmax = -1.0;
|
|
102
|
+
for (i = 0; i < number_of_points; i++) {
|
|
103
|
+
if (i != convex_point || p[i].flag == FLAG_OFF) {
|
|
104
|
+
take_coordinate_of_point(i, v2);
|
|
105
|
+
vsub_(v0, v2, v1, &n);
|
|
106
|
+
vunit_(v, v0, &n, &ierror);
|
|
107
|
+
d = vinpro_(uv, v, &n);
|
|
108
|
+
if (fabs(dmax - d) < EPS) {
|
|
109
|
+
ctemp[count] = i;
|
|
110
|
+
count++;
|
|
111
|
+
}
|
|
112
|
+
else if (dmax < d) {
|
|
113
|
+
dmax = d;
|
|
114
|
+
k = i;
|
|
115
|
+
ctemp[0] = i;
|
|
116
|
+
count = 1;
|
|
117
|
+
}
|
|
118
|
+
}
|
|
119
|
+
}
|
|
120
|
+
if (count >= 2) {
|
|
121
|
+
/*距離を用いて点を並び替える*/
|
|
122
|
+
sort_using_distance(ctemp, count, convex_point);
|
|
123
|
+
for (i = 0; i < count; i++) {
|
|
124
|
+
convex_point = ctemp[i];
|
|
125
|
+
p[convex_point].flag = FLAG_ON;
|
|
126
|
+
cp[number_of_convex_points] = convex_point;
|
|
127
|
+
number_of_convex_points++;
|
|
128
|
+
printf("凸多角形を構成する%d番目の点：%d\n", number_of_convex_points, convex_point);
|
|
129
|
+
}
|
|
130
|
+
}
|
|
131
|
+
else {
|
|
132
|
+
convex_point = k;
|
|
133
|
+
p[convex_point].flag = FLAG_ON;
|
|
134
|
+
cp[number_of_convex_points] = convex_point;
|
|
135
|
+
number_of_convex_points++;
|
|
136
|
+
printf("凸多角形を構成する%d番目の点：%d\n", number_of_convex_points, convex_point);
|
|
137
|
+
}
|
|
138
|
+
/*最初の点の戻れば終了*/
|
|
139
|
+
if (convex_point == start_point)break;
|
|
140
|
+
/*基準線の方向を設定する*/
|
|
141
|
+
determine_direction_of_base_line(uv, cp[number_of_convex_points - 2], convex_point);
|
|
142
|
+
}
|
|
143
|
+
}
|
|
144
|
+
|
|
145
|
+
void take_coordinate_of_point(int point_number, double v[])
|
|
146
|
+
{
|
|
147
|
+
v[0] = p[point_number].x;
|
|
148
|
+
v[1] = p[point_number].y;
|
|
149
|
+
|
|
150
|
+
}
|
|
151
|
+
|
|
152
|
+
int find_point_with_minimum_x(void)
|
|
153
|
+
{
|
|
154
|
+
int point_number;
|
|
155
|
+
int i;
|
|
156
|
+
double min;
|
|
157
|
+
|
|
158
|
+
point_number = 0;
|
|
159
|
+
min = p[0].x;
|
|
160
|
+
for (i = 1; i < number_of_points; i++) {
|
|
161
|
+
if (min > p[i].x) {
|
|
162
|
+
min = p[i].x;
|
|
163
|
+
point_number = i;
|
|
164
|
+
}
|
|
165
|
+
}
|
|
166
|
+
return point_number;
|
|
167
|
+
}
|
|
168
|
+
|
|
169
|
+
void determine_direction_of_base_line(double uv[], int point1, int point2)
|
|
170
|
+
{
|
|
171
|
+
double v1[2], v2[2], v[2];
|
|
172
|
+
int n = 2;
|
|
173
|
+
int error;
|
|
174
|
+
|
|
175
|
+
take_coordinate_of_point(point1, v1);
|
|
176
|
+
take_coordinate_of_point(point2, v2);
|
|
177
|
+
vsub_(v, v2, v1, &n);
|
|
178
|
+
vunit_(uv, v, &n, &error);
|
|
179
|
+
}
|
|
180
|
+
void sort_using_distance(int ct[], int n ,int p)
|
|
181
|
+
{
|
|
182
|
+
int i, j, k;
|
|
183
|
+
double v1[2], v2[2];
|
|
184
|
+
double dist[10];
|
|
185
|
+
double d;
|
|
186
|
+
double min, temp1;
|
|
187
|
+
int temp2;
|
|
188
|
+
|
|
189
|
+
/*２点間の距離の計算*/
|
|
190
|
+
take_coordinate_of_point(p, v1);
|
|
191
|
+
for (i = 0; i < n; i++) {
|
|
192
|
+
take_coordinate_of_point(ct[i], v2);
|
|
193
|
+
d = 0.0;
|
|
194
|
+
for (j = 0; j < 2; j++) {
|
|
195
|
+
d += (v2[j] - v1[j])*(v2[j] - v1[j]);
|
|
196
|
+
}
|
|
197
|
+
dist[i] = sqrt(d);
|
|
198
|
+
}
|
|
199
|
+
/*距離の昇順に点を並び替える*/
|
|
200
|
+
for (i = 0; i < n - 1; i++) {
|
|
201
|
+
min = dist[i];
|
|
202
|
+
k = i;
|
|
203
|
+
for (j = i + 1; j < n; j++) {
|
|
204
|
+
if (dist[j] < min) {
|
|
205
|
+
min = dist[j];
|
|
206
|
+
k = j;
|
|
207
|
+
}
|
|
208
|
+
}
|
|
209
|
+
temp1 = dist[i];
|
|
210
|
+
dist[i] = dist[k];
|
|
211
|
+
dist[k] = temp1;
|
|
212
|
+
temp2 = ct[i];
|
|
213
|
+
ct[i] = ct[k];
|
|
214
|
+
ct[k] = temp2;
|
|
215
|
+
}
|
|
216
|
+
}
|
|
217
|
+
|
|
218
|
+
/*単位ベクトル*/
|
|
219
|
+
void vunit_(double v[], double v0[], int *n, int *ierror)
|
|
220
|
+
{
|
|
221
|
+
int i;
|
|
222
|
+
double d = 0.0;
|
|
223
|
+
*ierror = V_NO_ERROR;
|
|
224
|
+
for (i = 0; i < *n; i++)d += v0[i] * v0[i];
|
|
225
|
+
if (d < 0.00000001) {
|
|
226
|
+
*ierror = V_ERROR;
|
|
227
|
+
return;
|
|
228
|
+
}
|
|
229
|
+
d = sqrt(d);
|
|
230
|
+
for (i = 0; i < *n; i++) v[i] = v0[i] / d;
|
|
231
|
+
return;
|
|
232
|
+
}
|
|
233
|
+
|
|
234
|
+
/*ベクトルの差*/
|
|
235
|
+
void vsub_(double v[], double v1[], double v2[], int *n)
|
|
236
|
+
{
|
|
237
|
+
int i;
|
|
238
|
+
for (i = 0; i < *n; i++)v[i] = v1[i] - v2[i];
|
|
239
|
+
return;
|
|
240
|
+
}
|
|
241
|
+
|
|
242
|
+
/*内積*/
|
|
243
|
+
double vinpro_(double v1[], double v2[], int *n)
|
|
244
|
+
{
|
|
245
|
+
int i;
|
|
246
|
+
double t = 0.0;
|
|
247
|
+
for (i = 0; i < *n; i++) t+= v1[i] * v2[i];
|
|
248
|
+
return t;
|
|
249
|
+
}
|
|
16
250
|
```
|
|
17
251
|
|
|
18
252
|
### 試したこと
|
1
書き足した
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -20,5 +20,4 @@
|
|
|
20
20
|
ここに問題に対して試したことを記載してください。
|
|
21
21
|
|
|
22
22
|
### 補足情報（FW/ツールのバージョンなど）
|
|
23
|
-
|
|
24
|
-
こ
|
|
23
|
+
このエラーメッセージについて教えていただきたいです。
|