#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N = 100;
const ld eps = 1e-9;
const ld inf = 2e9;
ll n;
ld s;
struct point{
ld x,y;
};
struct LINE{
point p1,p2;
};
LINE v[N + 4];
ld dist2[2*(N + 4)][2*(N + 4)];
point operator-(point &a, point &b){return {a.x - b.x,a.y - b.y};}
point operator+(point &a, point &b){return {a.x + b.x,a.y + b.y};}
ld dist(point x,point y){
x = x - y;
return sqrt(x.x*x.x + x.y*x.y);
}
ld cross(point a,point b){
return a.x*b.y - a.y*b.x;
}
ld dot(point a,point b){
return a.x*b.x + a.y*b.y;
}
bool intersect(LINE a,LINE b){
if(abs(cross(a.p1 - a.p2, b.p1 - b.p2)) < eps){
return 0;
}
ld x1 = cross(b.p1 - a.p1,b.p2 - a.p1)*cross(b.p1 - a.p2,b.p2 - a.p2);
ld x2 = cross(a.p1 - b.p1,a.p2 - b.p1)*cross(a.p1 - b.p2,a.p2 - b.p2);
return x1 < eps && x2 < -eps || x1 < -eps && x2 < eps;
}
ll hit(point a, point b) {
if(intersect({a,b},{{0,0},{400,1}}))return 1;
else return 0;
if (a.y < b.y)swap(a,b);
return a.y > 0 && b.y <= 0 && cross(a, b) < 0;
}
void add(ll i, ll j, point a, LINE b){
///gasim perpendiculara la drogatu asta
point p;
ld t = min((ld)1,max((ld)0,dot(a - b.p1,b.p2 - b.p1)/dot(b.p2 - b.p1,b.p2 - b.p1)));
p = {b.p1.x + t*(b.p2.x - b.p1.x),b.p1.y + t*(b.p2.y - b.p1.y)};
///this is how is used to do collision detection
for(ll k = 0;k < 4;k++){
if(intersect({p,a},{(k%2 == 0?s:-s),(k/2 == 0?s:-s)}))return;
}
if(abs((p.x + a.x)/2) <= s - eps && abs((p.y + a.y)/2) <= s - eps)return;
///FIND ANGLE
ld canddist = dist(p,a);
bool ord;
ord = hit(v[i].p1, a) ^ hit(a, p) ^ hit(p, v[j].p1);
//cout<<canddist<<' '<<i<<' '<<j<<' '<<a.x<<' '<<a.y<<' '<<p.x<<' '<<p.y<<'\n';
if(!ord){
dist2[i*2][j*2] = min(dist2[i*2][j*2],canddist);
dist2[j*2][i*2] = min(dist2[j*2][i*2],canddist);
dist2[i*2 + 1][j*2 + 1] = min(dist2[i*2 + 1][j*2 + 1],canddist);
dist2[j*2 + 1][i*2 + 1] = min(dist2[j*2 + 1][i*2 + 1],canddist);
}else{
dist2[i*2 + 1][j*2] = min(dist2[i*2 + 1][j*2],canddist);
dist2[j*2 + 1][i*2] = min(dist2[j*2 + 1][i*2],canddist);
dist2[i*2][j*2 + 1] = min(dist2[i*2][j*2 + 1],canddist);
dist2[j*2][i*2 + 1] = min(dist2[j*2][i*2 + 1],canddist);
}
}
void compute(ll i, ll j){
LINE a = v[i];
LINE b = v[j];
add(i, j, a.p1, b);
add(i, j, a.p2, b);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//cout<<fixed<<setprecision(6);
cin>>n>>s;
v[0] = {-s,-s,-s,-s};
v[1] = {-s, s,-s, s};
v[2] = { s,-s, s,-s};
v[3] = { s, s, s, s};
for(ll i = 4;i < n + 4;i++){
cin>>v[i].p1.x>>v[i].p1.y>>v[i].p2.x>>v[i].p2.y;
}
n+=4;
for(ll i = 0;i < 2*n;i++){
for(ll j = 0;j < 2*n;j++){
if(i == j){
dist2[i][j] = 0;
}else{
dist2[i][j] = inf;
}
}
}
for(ll i = 0;i < n;i++){
for(ll j = 0;j < n;j++){
if(i == j)continue;
compute(i, j);
}
}
for(ll i = 0;i < 2*n;i++){
for(ll j = 0;j < 2*n;j++){
for(ll k = 0;k < 2*n;k++){
dist2[j][k] = min(dist2[j][k],dist2[j][i] + dist2[i][k]);
}
}
}
ld ans = 16*s;
for(ll i = 0;i < n;i++){
ans = min(ans,dist2[i*2][i*2 + 1]);
}
cout<<ans<<'\n';
return 0;
}
Compilation message
fences.cpp: In function 'bool intersect(LINE, LINE)':
fences.cpp:36:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
36 | return x1 < eps && x2 < -eps || x1 < -eps && x2 < eps;
| ~~~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
472 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
472 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
540 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
540 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
600 KB |
Output is correct |
34 |
Correct |
1 ms |
344 KB |
Output is correct |
35 |
Correct |
0 ms |
500 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
472 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
540 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
540 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
600 KB |
Output is correct |
34 |
Correct |
1 ms |
344 KB |
Output is correct |
35 |
Correct |
0 ms |
500 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
0 ms |
348 KB |
Output is correct |
44 |
Correct |
75 ms |
1116 KB |
Output is correct |
45 |
Correct |
71 ms |
1112 KB |
Output is correct |
46 |
Correct |
70 ms |
1132 KB |
Output is correct |
47 |
Correct |
75 ms |
1112 KB |
Output is correct |
48 |
Correct |
74 ms |
1116 KB |
Output is correct |
49 |
Correct |
73 ms |
1116 KB |
Output is correct |
50 |
Correct |
80 ms |
1112 KB |
Output is correct |
51 |
Correct |
62 ms |
1368 KB |
Output is correct |
52 |
Correct |
63 ms |
1112 KB |
Output is correct |
53 |
Correct |
69 ms |
1116 KB |
Output is correct |
54 |
Correct |
71 ms |
1112 KB |
Output is correct |
55 |
Correct |
68 ms |
1128 KB |
Output is correct |
56 |
Correct |
66 ms |
1116 KB |
Output is correct |
57 |
Correct |
68 ms |
1112 KB |
Output is correct |
58 |
Correct |
69 ms |
1112 KB |
Output is correct |
59 |
Correct |
65 ms |
1132 KB |
Output is correct |
60 |
Correct |
68 ms |
1116 KB |
Output is correct |
61 |
Correct |
67 ms |
1128 KB |
Output is correct |
62 |
Correct |
1 ms |
348 KB |
Output is correct |
63 |
Correct |
1 ms |
348 KB |
Output is correct |
64 |
Correct |
63 ms |
1368 KB |
Output is correct |
65 |
Correct |
70 ms |
1360 KB |
Output is correct |
66 |
Correct |
60 ms |
1116 KB |
Output is correct |
67 |
Correct |
74 ms |
1116 KB |
Output is correct |
68 |
Correct |
64 ms |
1116 KB |
Output is correct |
69 |
Correct |
69 ms |
1132 KB |
Output is correct |
70 |
Correct |
58 ms |
856 KB |
Output is correct |
71 |
Correct |
66 ms |
1112 KB |
Output is correct |
72 |
Correct |
69 ms |
1128 KB |
Output is correct |