Submission #1011171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011171		snpmrnhlol	Fences (JOI18_fences)	C++17	100 / 100	80 ms	1368 KiB

fences

#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 (stderr)

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;
      |            ~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49