Submission #985637

#	Time	Username	Problem	Language	Result	Execution time	Memory
985637		alextodoran	Fences (JOI18_fences)	C++17	100 / 100	330 ms	8992 KiB

fences

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N_MAX = 100;
const int V_MAX = N_MAX * 4 + 4;
const ld INF = LLONG_MAX;
const int R = 40;

int N, S;
struct Point {
    ld x, y;
};
ld dist (Point A, Point B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
struct Segment {
    Point A, B;
    ld len () {
        return dist(A, B);
    }
};
Segment fence[N_MAX + 2];

Point project (Point P, Segment s) {
    if (s.A.x == s.B.x) {
        return Point{s.A.x, P.y};
    } else if (s.A.y == s.B.y) {
        return Point{P.x, s.A.y};
    } else {
        ld mAB = (ld) (s.A.y - s.B.y) / (s.A.x - s.B.x);
        ld mPQ = -1 / mAB;
        Point Q;
        Q.x = (P.y - s.A.y - P.x * mPQ + s.A.x * mAB) / (mAB - mPQ);
        Q.y = P.y + (Q.x - P.x) * mPQ;
        return Q;
    }
}
bool is_inside (Point P, Segment s) {
    return (min(s.A.x, s.B.x) <= P.x && P.x <= max(s.A.x, s.B.x)
         && min(s.A.y, s.B.y) <= P.y && P.y <= max(s.A.y, s.B.y));
}
bool check (Segment s) {
    Point mid = Point{(s.A.x + s.B.x) / 2, (s.A.y + s.B.y) / 2};
    if (-S < mid.x && mid.x < S && -S < mid.y && mid.y < S) {
        return false;
    }
    for (int side = 0; side < 4; side++) {
        if (s.A.y > s.B.y) {
            swap(s.A, s.B);
        }
        if (s.A.y < S && S < s.B.y) {
            ld x;
            if (s.A.x != s.B.x) {
                x = s.A.x + (ld) (s.B.x - s.A.x) * (S - s.A.y) / (s.B.y - s.A.y);
            } else {
                x = s.A.x;
            }
            if (-S < x && x < S) {
                return false;
            }
        }
        swap(s.A.x, s.A.y); s.A.x *= -1;
        swap(s.B.x, s.B.y); s.B.x *= -1;
    }
    return true;
}

Point corner[4];

int V;
Point get_point (int u) {
    if (u <= N * 2) {
        if (u % 2 == 1) {
            return fence[u / 2 + 1].A;
        } else {
            return fence[u / 2].B;
        }
    } else {
        return corner[u - N * 2 - 1];
    }
}
struct Edge {
    int to;
    ld len;
    bool trigo;
};
bool is_trigo (Segment s) {
    return (s.A.x * s.B.y - s.A.y * s.B.x > 0);
}
vector <Edge> out[V_MAX + 2];
void add_edge (int u, int v, Segment s, bool is_fence = false) {
    Point A = s.A, P = s.B, B = get_point(v);
    ld len = (is_fence == false ? s.len() : 0);
    bool trigo = is_trigo(Segment{A, B});
    if (P.x != B.x || P.y != B.y) {
        if (is_trigo(Segment{A, P}) != trigo && is_trigo(Segment{P, B}) != trigo) {
            trigo = !trigo;
        }
    }
    out[u].push_back(Edge{v, len, trigo});
    swap(s.A, s.B); trigo = !trigo;
    out[v].push_back(Edge{u, len, trigo});
}

int get_quad (Point P) {
    if (P.x >= 0 && P.y > 0) {
        return 0;
    } else if (P.x < 0 && P.y >= 0) {
        return 1;
    } else if (P.x <= 0 && P.y < 0) {
        return 2;
    } else {
        return 3;
    }
}

ld min_dist[V_MAX + 2][R * 2 + 2];
bool seen[V_MAX + 2][R * 2 + 2];

struct Path {
    int u;
    int var;
    ld len;
};
bool operator < (const Path &p1, const Path &p2) {
    return p1.len > p2.len;
}

ld answer = LLONG_MAX;

void Dijkstra (int start) {
    priority_queue <Path> q;
    for (int u = 1; u <= V; u++) {
        for (int var = -R; var <= R; var++) {
            min_dist[u][var + R] = INF;
            seen[u][var + R] = false;
        }
    }
    min_dist[start][0 + R] = 0;
    q.push(Path{start, 0, 0});
    while (q.empty() == false) {
        Path p = q.top(); q.pop();
        if (seen[p.u][p.var] == true) {
            continue;
        }
        seen[p.u][p.var] = true;
        if (p.len > answer) {
            continue;
        }
        if (p.u == start && p.var == 4) {
            answer = p.len;
        }
        Point A = get_point(p.u);
        for (Edge e : out[p.u]) {
            Point B = get_point(e.to);
            Path pe; pe.u = e.to; pe.len = p.len + e.len;
            int delta = get_quad(B) - get_quad(A);
            if (e.trigo == true) {
                if (delta < 0) {
                    delta += 4;
                }
            } else {
                if (delta > 0) {
                    delta -= 4;
                }
            }
            pe.var = p.var + delta;
            if (-R <= pe.var && pe.var <= R) {
                if (pe.len < min_dist[pe.u][pe.var + R]) {
                    min_dist[pe.u][pe.var + R] = pe.len;
                    q.push(pe);
                }
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);

    cin >> N >> S;
    for (int i = 1; i <= N; i++) {
        cin >> fence[i].A.x >> fence[i].A.y;
        cin >> fence[i].B.x >> fence[i].B.y;
    }
    corner[0] = Point{S, S};
    corner[1] = Point{-S, S};
    corner[2] = Point{-S, -S};
    corner[3] = Point{S, -S};
    for (int c = 0; c < 4; c++) {
        add_edge(N * 2 + 1 + c, N * 2 + 1 + (c + 1) % 4, Segment{corner[c], corner[(c + 1) % 4]});
    }
    V = N * 2 + 4;
    for (int i = 1; i <= N; i++) {
        add_edge(i * 2 - 1, i * 2, fence[i], true);
        for (int j = i + 1; j <= N; j++) {
            Segment A1A2 = Segment{fence[i].A, fence[j].A};
            if (check(A1A2) == true) {
                add_edge(i * 2 - 1, j * 2 - 1, A1A2);
            }
            Segment A1B2 = Segment{fence[i].A, fence[j].B};
            if (check(A1B2) == true) {
                add_edge(i * 2 - 1, j * 2, A1B2);
            }
            Segment B1A2 = Segment{fence[i].B, fence[j].A};
            if (check(B1A2) == true) {
                add_edge(i * 2, j * 2 - 1, B1A2);
            }
            Segment B1B2 = Segment{fence[i].B, fence[j].B};
            if (check(B1B2) == true) {
                add_edge(i * 2, j * 2, B1B2);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                Point P = project(fence[i].A, fence[j]);
                Segment AP = Segment{fence[i].A, P};
                if (is_inside(P, fence[j]) == true && check(AP) == true) {
                    add_edge(i * 2 - 1, j * 2 - 1, AP);
                    add_edge(i * 2 - 1, j * 2, AP);
                }
                Point Q = project(fence[i].B, fence[j]);
                Segment BQ = Segment{fence[i].B, Q};
                if (is_inside(Q, fence[j]) == true && check(BQ) == true) {
                    add_edge(i * 2, j * 2 - 1, BQ);
                    add_edge(i * 2, j * 2, BQ);
                }
            }
        }
        for (int c = 0; c < 4; c++) {
            Segment AC = Segment{fence[i].A, corner[c]};
            Segment BC = Segment{fence[i].B, corner[c]};
            if (check(AC) == true) {
                add_edge(i * 2 - 1, N * 2 + 1 + c, AC);
            }
            if (check(BC) == true) {
                add_edge(i * 2, N * 2 + 1 + c, BC);
            }
        }
        for (int c = 0; c < 4; c++) {
            Point P = project(corner[c], fence[i]);
            Segment CP = Segment{corner[c], P};
            if (is_inside(P, fence[i]) == true && check(CP) == true) {
                add_edge(N * 2 + 1 + c, i * 2 - 1, CP);
                add_edge(N * 2 + 1 + c, i * 2, CP);
            }
        }
    }
    for (int u = 1; u <= V; u++) {
        Point A = get_point(u);
        Dijkstra(u);
    }
    cout << answer << "\n";

    return 0;
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:200:23: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  200 |     corner[0] = Point{S, S};
      |                       ^
fences.cpp:200:26: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  200 |     corner[0] = Point{S, S};
      |                          ^
fences.cpp:201:23: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  201 |     corner[1] = Point{-S, S};
      |                       ^~
fences.cpp:201:27: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  201 |     corner[1] = Point{-S, S};
      |                           ^
fences.cpp:202:23: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  202 |     corner[2] = Point{-S, -S};
      |                       ^~
fences.cpp:202:27: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  202 |     corner[2] = Point{-S, -S};
      |                           ^~
fences.cpp:203:23: warning: narrowing conversion of 'S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  203 |     corner[3] = Point{S, -S};
      |                       ^
fences.cpp:203:26: warning: narrowing conversion of '- S' from 'int' to 'ld' {aka 'long double'} [-Wnarrowing]
  203 |     corner[3] = Point{S, -S};
      |                          ^~
fences.cpp:266:15: warning: variable 'A' set but not used [-Wunused-but-set-variable]
  266 |         Point A = get_point(u);
      |               ^

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