oj.uz

Submission #1010925

# Submission time Handle Problem Language Result Execution time Memory
1010925 2024-06-29T14:28:30 Z snpmrnhlol Fences (JOI18_fences) C++17
18 / 100
 1 ms 604 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 100;
const ld eps = 1e-9;
const ld inf = 2e9;
int n;
ld  s;
struct point{
    ld x,y;
};
struct LINE{
    point p1,p2;
};
LINE v[N + 4];
ld dist2[N + 4][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;
}
int hit(point a, point b) {
    return intersect({a,b},{0,0,0,inf});
	if (a.y < b.y)swap(a,b);
	return a.y > 0 && b.y <= 0 && cross(a, b) < 0;
}
void add(int i, int 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(int 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(int i, int 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(int 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(int i = 0;i < 2*n;i++){
        for(int j = 0;j < 2*n;j++){
            if(i == j){
                dist2[i][j] = 0;
            }else{
                dist2[i][j] = inf;
            }
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(i == j)continue;
            compute(i, j);
        }
    }
    for(int i = 0;i < 2*n;i++){
        for(int j = 0;j < 2*n;j++){
            for(int k = 0;k < 2*n;k++){
                dist2[j][k] = min(dist2[j][k],dist2[j][i] + dist2[i][k]);
            }
        }
    }

    ld ans = 16*s;
    for(int 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:35:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     return x1 < eps && x2 < -eps || x1 < -eps && x2 < eps;
      |            ~~~~~~~~~^~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# 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 0 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 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 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 1 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 348 KB Output is correct

Subtask #2
0 / 33.0

# 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 0 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 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 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 1 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 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 352 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 352 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Incorrect 0 ms 352 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 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 0 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 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 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 1 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 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 352 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 352 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Incorrect 0 ms 352 KB Output isn't correct
43 Halted 0 ms 0 KB -