1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include <math.h>
#include <stdio.h>
#define ABS(x) (((x) < 0) ? -(x) : (x))
#define SQR(x) ((x) * (x))
#define DET(a, b, c, d) ((a) * (d) - (b) * (c))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
typedef struct {
long x, y;
} poin_t;
typedef struct {
float x, y;
} fpoin_t;
long area2(poin_t A, poin_t B, poin_t C)
{
return ABS(DET(C.x - A.x, A.x - B.x, C.y - A.y, A.y - B.y));
}
int main()
{
FILE *f = fopen("DG.INP", "r");
char n, i, c = 0, b;
poin_t M, N, P, Q, polygon[101];
fpoin_t tmp, intersections[2];
long Mout = 0, Nout, d;
double res;
fscanf(f, "%hhd", &n);
for (i = 0; i < n; i++)
fscanf(f, "%ld %ld", &polygon[i].x, &polygon[i].y);
fscanf(f, "%ld %ld %ld %ld", &M.x, &M.y, &N.x, &N.y);
fclose(f);
f = fopen("DG.OUT", "w");
if (M.x == N.x && M.y == N.y) {
fputs("0\n", f);
fclose(f);
return 0;
}
for (i = 1; i < n - 1; i++)
Mout += area2(*polygon, polygon[i], polygon[i + 1]);
for (Nout = Mout, polygon[n] = *polygon, i = 0; i < n; i++) {
Mout -= area2(M, polygon[i], polygon[i + 1]);
Nout -= area2(N, polygon[i], polygon[i + 1]);
}
if (!Mout && !Nout) {
fprintf(f, "%ld\n",
(long) (sqrt(SQR(M.x - N.x) + SQR(M.y - N.y)) * 100));
fclose(f);
return 0;
}
for (i = 0; i < n; i++) {
P = polygon[i];
Q = polygon[i + 1];
d = DET(M.x - N.x, M.y - N.y, P.x - Q.x, P.y - Q.y);
if (!d)
continue;
tmp.x = DET(DET(M.x, M.y, N.x, N.y), M.x - N.x,
DET(P.x, P.y, Q.x, Q.y), P.x - Q.x) / (double) d;
tmp.y = DET(DET(M.x, M.y, N.x, N.y), M.y - N.y,
DET(P.x, P.y, Q.x, Q.y), P.y - Q.y) / (double) d;
if (tmp.x < MAX(MIN(M.x, N.x), MIN(P.x, Q.x))
|| tmp.x > MIN(MAX(M.x, N.x), MAX(P.x, Q.x))
|| tmp.y < MAX(MIN(M.y, N.y), MIN(P.y, Q.y))
|| tmp.y > MIN(MAX(M.y, N.y), MAX(P.y, Q.y)))
continue;
for (b = d = 0; d < c; d++)
if (intersections[d].x == tmp.x
&& intersections[d].y == tmp.y)
b = 1;
if (b)
continue;
intersections[c].x = tmp.x;
intersections[c].y = tmp.y;
c++;
}
if (!Mout && c)
res = SQR(M.x - intersections[0].x)
+ SQR(M.y - intersections[0].y);
else if (!Nout && c)
res = SQR(N.x - intersections[0].x)
+ SQR(N.y - intersections[0].y);
else if (c == 2)
res = SQR(intersections[0].x - intersections[1].x)
+ SQR(intersections[0].y - intersections[1].y);
else
res = 0;
fprintf(f, "%ld\n", (long) (sqrt(res) * 100));
fclose(f);
return 0;
}
|
