#include <bits/stdc++.h>
using namespace std;
struct Point {
int x;
int y;
};
bool compareOnX(Point f1, Point f2) {
return f1.x < f2.x;
}
// Binary search for largest index j in array v
// so that v[j] < number.
int binarySearch(const vector<int>& v, int lo, int hi, int number) {
while (hi > lo + 1) {
int mid = lo + (hi - lo) / 2;
if (v[mid] >= number) {
hi = mid;
} else {
lo = mid;
}
}
if (v[hi] < number) {
return hi;
} else if (v[lo] < number) {
return lo;
} else {
return -1;
}
}
// O(N * log(K)) solution
int longestIncreasingSubsequenceEfficient(const vector<int>& a) {
vector<int> dp(a.size(), 0);
if (a.size() == 0) return 0;
dp[0] = 1; // Length of LIS ending on first element is 1.
vector<int> smallest_last_element_for_length(a.size(), 0);
smallest_last_element_for_length[0] = a[0]; // Careful: element with index 0 is for length 1.
int k = 1; // Length of longest increasing subsequence seen so far.
// Loop over subproblems.
for (int i = 1; i < a.size(); ++i) {
// Binary search for largest index j in smallest_last_element_for_length
// so that smallest_last_element_for_length[j] < a[i].
int lo = 0;
int hi = min(i - 1, k - 1); // hi cannot be larger than largest length so far.
int max_len = binarySearch(smallest_last_element_for_length, lo, hi, a[i]) + 1;
dp[i] = 1 + max_len;
if (dp[i] > k) { // If larger LIS length than what we've seen uptil now.
// Update state variables.
k = dp[i];
smallest_last_element_for_length[k - 1] = a[i];
} else {
if (a[i] < smallest_last_element_for_length[dp[i] - 1]) {
smallest_last_element_for_length[dp[i] - 1] = a[i];
}
}
}
return k;
}
// O(N^2) solution
int longestIncreasingSubsequence(vector<int> a) {
vector<int> dp(a.size(), 0);
if (a.size() == 0) return 0;
dp[0] = 1; // length of LIS ending on first element is 1.
for (int i = 1; i < a.size(); ++i) {
// Max over LIS lengths where last element smaller than a[i].
int mx = 0;
for (int j = 0; j < i; ++j) {
if (dp[j] > mx && a[j] < a[i]) {
mx = dp[j];
}
}
dp[i] = 1 + mx;
}
// Max of all LIS lengths.
int ans = 0;
for (int i = 0; i < dp.size(); ++i) {
if (dp[i] > ans) {
ans = dp[i];
}
}
return ans;
}
double pathLength(Point p1, Point p2, int number_of_fountains) {
// Also include scenario where number_of_fountains == 0.
// Also include scenario where start and stop have same x or y value.
double manhattan_path_length = 100 * ((p2.x - p1.x) + (p2.y - p1.y));
double radius = 10;
double quarter_circumference = M_PI * radius / 2;
if ((p1.x == p2.x) || (p1.y == p2.y)) {
if (number_of_fountains == 0) {
return manhattan_path_length;
} else if (number_of_fountains == 1) {
return manhattan_path_length - 2 * radius + 2 * quarter_circumference;
} else {
cout << "Error. This should never happen." << endl;
return -1;
}
} else {
return manhattan_path_length - number_of_fountains * (2 * radius - quarter_circumference);
}
}
void solve() {
int x1, y1, x2, y2, N;
cin >> x1 >> y1 >> x2 >> y2;
cin >> N;
// Make start the leftmost point of the two.
Point start = {x1, y1};
Point stop = {x2, y2};
if (start.x > stop.x) {
Point tmp = start;
start = stop;
stop = tmp;
}
// If start above stop, flip around x axis.
bool flip_around_x_axis = false;
if (start.y > stop.y) {
flip_around_x_axis = true;
start.y = - start.y;
stop.y = - stop.y;
}
vector<Point> fountains;
// Add fountains if within rectangle.
for (int i = 0; i < N; ++i) {
int x, y;
cin >> x >> y;
if (flip_around_x_axis) {
y = - y;
}
if (x >= start.x && x <= stop.x &&
y >= start.y && y <= stop.y) {
fountains.push_back({x, y});
}
}
// Sort fountains along x.
sort(fountains.begin(), fountains.end(), compareOnX);
// Find number of fountains on optimal path.
vector<int> y_coords;
y_coords.reserve(fountains.size());
for (int i = 0; i < fountains.size(); ++i) {
y_coords.push_back(fountains[i].y);
}
int number_of_fountains = longestIncreasingSubsequence(y_coords);
// Calculate path length from number_of_fountains.
double path_length = pathLength(start, stop, number_of_fountains);
cout.precision(18);
cout << path_length << endl;
}
void testlongestIncreasingSubsequenceEfficient() {
vector<int> array1 = {1, 2, 3, 4, 5};
assert(longestIncreasingSubsequenceEfficient(array1) == 5);
vector<int> array2 = {-1, 4, -3, 5, 6};
assert(longestIncreasingSubsequenceEfficient(array2) == 4);
vector<int> array3 = {0, 10, 2, 3, 4, 22, 6, -8, -7, -6, -5, -4};
assert(longestIncreasingSubsequenceEfficient(array3) == 5);
vector<int> array4 = {10, 2, 3, 4, 5};
assert(longestIncreasingSubsequenceEfficient(array4) == 4);
vector<int> array5(200000);
for (int i = 0; i < array5.size(); ++i) {
array5[i] = i;
}
assert(longestIncreasingSubsequenceEfficient(array5) == array5.size());
}
int main() {
// freopen("/Users/simon/Downloads/test.in", "r", stdin);
// testlongestIncreasingSubsequenceEfficient();
// freopen("/Users/simon/Downloads/test.out", "w", stdout);
solve();
}