Submission #1243027

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <chrono>
#include <sstream>
#include <iomanip>
using namespace std;
#define MOD 1000000007
#define PI 3.14159265358979
#define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v) for (auto i : v)
#define D(x) cout << x << endl
#define d(x) cout << x
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pub(x) push_back(x)
#define pob() pop_back()
#define puf(x) push_front(x)
#define pof() pop_front()
#define mp(x, y) make_pair((x), (y))
#define fi first
#define se second
#define setp(x) setprecision(x)
#define mset(m, v) memset(m, v, sizeof(m))
static const int INF = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }

//static const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//#define int ll

int main() { 
        int n;
        cin >> n;
        int start, goal;
        cin >> start >> goal;
        vi l(n + 1), r(n + 1);
        rep(i, n + 1) cin >> l[i] >> r[i];
        l[0] = r[0] = start;
        l[n] = r[n] = goal;
        double ans = 0;
        int y = 0, x = start;
        auto cmp = [&](int ay, int ax, int by, int bx) {
                return (ax - x) * (ll)(by - y) - (ay - y) * (ll)(bx - x) < 0;
        };
        while (y < n) {
                int ly = y, ry = y;
                int lx = x - 1, rx = x + 1;
                reu(ny, y + 1, n + 1) {
                        if (cmp(ny, r[ny], ly, lx) && ly != y) {
                                ans += hypot(ly - y, l[ly] - x);
                                y = ly;
                                x = l[ly];
                                goto next;
                        }
                        if (cmp(ry, rx, ny, l[ny]) && ry != y) {
                                ans += hypot(ry - y, r[ry] - x);
                                y = ry;
                                x = r[ry];
                                goto next;
                        }
                        if (cmp(ny, r[ny], ry, rx)) {
                                ry = ny;
                                rx = r[ny];
                        }
                        if (cmp(ly, lx, ny, l[ny])) {
                                ly = ny;
                                lx = l[ny];
                        }
                }
                ans += hypot(n - y, goal - x);
                y = n;
                x = goal;
next:;
        }
        cout << setp(15) << ans << endl;
        return 0;
}

Submission Info

Judge Result