Submission #97887

#	Time	Username	Problem	Language	Result	Execution time	Memory
97887		Alexa2001	Fences (JOI18_fences)	C++17	100 / 100	524 ms	3192 KiB

fences

#include <bits/stdc++.h>
#define x real()
#define y imag()

using namespace std;

const int Nmax = 210;
const long double eps = 1e-6;

typedef complex<long double> point;

long double dist[Nmax][2][Nmax][2];
int S, N;
point a[Nmax], O, W;
point S1[10], S2[10];


int Pair(int k)
{
    if(k >= 2*N) return -1;
    return k^1;
}

long double distanta(point A, point B)
{
    return abs(A - B);
}

long double cross(point a, point b)
{
    return (conj(a) * b).y;
}

long double dot(point a, point b)
{
    return (conj(a) * b).x;
}

bool on_segm(point A, point B, point C) /// este A pe segmentul [BC]?
{
    return distanta(A, B) + distanta(A, C) - distanta(B, C) < eps;
}

point reflect(point A, point B, point C)
{
    A -= B; C -= B;
    return B + (conj(A / C)) * C;
}

point perp(point A, point B, point C) /// perpendiculara din A pe dreapta BC
{
    return (A + reflect(A, B, C)) / (long double) 2;
}

point intersect(point a, point b, point c, point d)
{
    b -= a; c -= a; d -= a;
    long double c1 = cross(c, b), c2 = cross(d, b);
    return a + (c1 * d - c2 * c) / (c1 - c2);
}

bool inters_segm(point a, point b, point c, point d)
{
    if(cross(c-a, b-a) == cross(d-a, b-a)) return 0; /// paralele
    point P = intersect(a, b, c, d);
    return on_segm(P, a, b) && on_segm(P, c, d);
}

bool pass(point a, point b)
{
    return inters_segm(a, b, O, W);
}

bool is_ok(point A, point B) /// trece dreapta AB prin interiorul patratului initial?
{
    int i;
    for(i=0; i<4; ++i)
        if(inters_segm(A, B, S1[i], S2[i])) return 0;
    return 1;
}

void add_edge(int s, int t, long double D, bool p)
{
    dist[s][0][t][p] = min(dist[s][0][t][p], D);
    dist[s][1][t][p^1] = min(dist[s][1][t][p^1], D);
    swap(s, t);
    dist[s][0][t][p] = min(dist[s][0][t][p], D);
    dist[s][1][t][p^1] = min(dist[s][1][t][p^1], D);
}

void find_edge(int s, int t)
{
    if(Pair(s) == t) /// puncte de pe acelasi segment
    {
        add_edge(s, t, 0, pass(a[s], a[t]));
        return;
    }

    if(is_ok(a[s], a[t]))
        add_edge(s, t, distanta(a[s], a[t]), pass(a[s], a[t]));

    int z = Pair(s);
    if(z != -1)
    {
        point P = perp(a[t], a[s], a[z]);
        if(on_segm(P, a[s], a[z]) && is_ok(a[t], P))
            add_edge(s, t, distanta(a[t], P), pass(a[t], P) ^ pass(P, a[s]));
    }

    swap(s, t);
    z = Pair(s);
    if(z != -1)
    {
        point P = perp(a[t], a[s], a[z]);
        if(on_segm(P, a[s], a[z]) && is_ok(a[t], P))
            add_edge(s, t, distanta(a[t], P), pass(a[t], P) ^ pass(P, a[s]));
    }
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, n;
    cin >> N >> S;
    for(i=0; i<N; ++i)
    {
        long double X, Y;
        cin >> X >> Y;
        a[2*i] = {X, Y};
        cin >> X >> Y;
        a[2*i+1] = {X, Y};
    }

    n = 2*N;
    a[n++] = {-S, S};
    a[n++] = {S, S};
    a[n++] = {S, -S};
    a[n++] = {-S, -S};

    O = {0, 0}; W = {251, 257};

    S1[0] = S2[3] = a[2*N] + point(eps, -eps);
    S1[1] = S2[0] = a[2*N+1] + point(-eps, -eps);
    S1[2] = S2[1] = a[2*N+2] + point(-eps, +eps);
    S1[3] = S2[2] = a[2*N+3] + point(eps, +eps);



    int j, k, i2, j2, k2;

    for(i=0; i<n; ++i)
        for(i2=0; i2<2; ++i2)
        {
            for(j=0; j<n; ++j)
                for(j2=0; j2<2; ++j2)
                    dist[i][i2][j][j2] = 10 * S;
            dist[i][i2][i][i2] = 0;
        }

    for(i=0; i<n; ++i)
        for(j=i+1; j<n; ++j)
            find_edge(i, j);

    for(k=0; k<n; ++k)
        for(k2=0; k2<2; ++k2)
            for(i=0; i<n; ++i)
                for(i2=0; i2<2; ++i2)
                    for(j=0; j<n; ++j)
                        for(j2=0; j2<2; ++j2)
                            dist[i][i2][j][j2] = min(dist[i][i2][j][j2], dist[i][i2][k][k2] + dist[k][k2][j][j2]);

    long double ans = 10 * S;
    for(i=0; i<n; ++i)
    {
        ans = min(ans, dist[i][0][i][1]);
     //   assert(dist[i][0][i][1] == dist[i][1][i][0]);
    }

    cout << setprecision(10) << fixed;
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:137:15: warning: narrowing conversion of '- S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {-S, S};
               ^~
fences.cpp:137:20: warning: narrowing conversion of 'S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {-S, S};
                    ^
fences.cpp:138:19: warning: narrowing conversion of 'S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {S, S};
                   ^
fences.cpp:138:19: warning: narrowing conversion of 'S' from 'int' to 'long double' inside { } [-Wnarrowing]
fences.cpp:139:20: warning: narrowing conversion of 'S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {S, -S};
                    ^
fences.cpp:139:18: warning: narrowing conversion of '- S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {S, -S};
                  ^~
fences.cpp:140:15: warning: narrowing conversion of '- S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {-S, -S};
               ^~
fences.cpp:140:19: warning: narrowing conversion of '- S' from 'int' to 'long double' inside { } [-Wnarrowing]
     a[n++] = {-S, -S};
                   ^~

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