Language: C++


#ifdef LOCAL
  #define debug_echo(expr) cout << expr;
#else
  #define debug_echo(expr)
#endif

#define rep(i, n) for (int i = 0; i < n; i++)

#include <iostream>
#include <assert.h>
#define _USE_MATH_DEFINES
#include <cmath>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

template<class T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    bool isfirst = false;
    for (const T& e : v) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "]";
    return out;
}
template<class T>
ostream& operator <<(ostream& out, const set<T>& s) {
    out << "{";
    bool isfirst = false;
    for (const T& e : s) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "}";
    return out;
}
template<class A, class B>
ostream& operator <<(ostream& out, const pair<A, B>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}
template<class K, class V>
ostream& operator <<(ostream& out, const map<K, V>& s) {
    out << "{";
    bool isfirst = false;
    for (const auto& e : s) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "}";
    return out;
}

//
// Implementation
//

#define MAX_W 100000000
#define MAX_N 200000
// #define PI 3.1415926

#define SWAP(x, y) { auto tmp = x; x = y; y = tmp; }

double dp[MAX_W+1][MAX_W+1];
int inx1, iny1, inx2, iny2;
int N;
set<pair<int, int> > fountains;

bool on_fountain(int x, int y) {
    auto it = fountains.find(make_pair(x, y));
    if (it != fountains.end()) {
        return true;
    } else {
        return false;
    }
}
double get_distance(int prevx, int prevy, int x, int y, int nextx, int nexty) {
    double res = 100.0;
    if (on_fountain(x, y)) {
        if (prevx == -1 || prevy == -1) {
            // discard
        } else if (prevx != nextx && prevy == nexty) { // VERT
            res += -10.0 + 20.0*M_PI/4.0;
        } else if (prevy != nexty && prevx == nextx) { // HORI
            res += -10.0 + 20.0*M_PI/4.0;
        } else {
            res -= 10.0;
        }
    }
    if (on_fountain(nextx, nexty)) {
        res += -10.0 + 20.0*M_PI/4.0;
    }
    return res;
}

double dp1(int prevx, int prevy, int x, int y) {
    if (dp[x][y] >= 0){
        return dp[x][y];
    }
    double res;
    if (x == inx2 && y == iny2) {
        res = 0;
    } else if (x == inx2) {
        res = dp1(x, y, x, y+1) + get_distance(prevx, prevy, x, y, x, y+1);
    } else if (y == iny2) {
        res = dp1(x, y, x+1, y) + get_distance(prevx, prevy, x, y, x+1, y);
    } else {
        double res1 = dp1(x, y, x+1, y) + get_distance(prevx, prevy, x, y, x+1, y);
        double res2 = dp1(x, y, x, y+1) + get_distance(prevx, prevy, x, y, x, y+1);
        // int res3 = dp1(x+1, y+1) + get_distance(x, y, x+1, y+1);
        res = min(res1, res2);
    }
    return dp[x][y] = res;
}

int main() {
    cin >> inx1 >> iny1 >> inx2 >> iny2;
    cin >> N;
    rep(i, N) {
        int first, second;
        cin >> first >> second;
        fountains.insert(make_pair(first, second));
    }
    memset(dp, -1, sizeof(dp));

    if (inx1 > inx2) {
        SWAP(inx1, inx2);
    }
    if (iny1 > iny2) {
        SWAP(iny1, iny2);
    }

    printf("%f\n", dp1(-1, -1, inx1, iny1));
}


Compiler output:
/tmp/ccRhePd8.o: in function `on_fountain(int, int)':
a.cc:(.text+0x2f): relocation truncated to fit: R_X86_64_PC32 against symbol `fountains' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x42): relocation truncated to fit: R_X86_64_PC32 against symbol `fountains' defined in .bss section in /tmp/ccRhePd8.o
/tmp/ccRhePd8.o: in function `dp1(int, int, int, int)':
a.cc:(.text+0x1cc): relocation truncated to fit: R_X86_64_PC32 against symbol `inx2' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x1d7): relocation truncated to fit: R_X86_64_PC32 against symbol `iny2' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x1f0): relocation truncated to fit: R_X86_64_PC32 against symbol `inx2' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x248): relocation truncated to fit: R_X86_64_PC32 against symbol `iny2' defined in .bss section in /tmp/ccRhePd8.o
/tmp/ccRhePd8.o: in function `main':
a.cc:(.text+0x3b0): relocation truncated to fit: R_X86_64_PC32 against symbol `inx1' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x3cc): relocation truncated to fit: R_X86_64_PC32 against symbol `iny1' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x3e1): relocation truncated to fit: R_X86_64_PC32 against symbol `inx2' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x3f6): relocation truncated to fit: R_X86_64_PC32 against symbol `iny2' defined in .bss section in /tmp/ccRhePd8.o
a.cc:(.text+0x408): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status