Submission #1540617

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }

const double PI = acos(-1);

int X[200050], Y[200050];

int flip(int s) {
  return 100000000 - s - 1;
}

int lis(const vector<int>& a) {
  const int n = a.size();
  if (n == 0) {
    return 0;
  }
  
  vector<int> A(n, INF), id(n);
  for (int i = 0; i < n; ++i) {
    id[i] = distance(A.begin(), lower_bound(A.begin(), A.end(), a[i]));
    A[id[i]] = a[i];
  }
  return *max_element(id.begin(), id.end()) + 1;
}

int main() {
  int sx = in();
  int sy = in();
  int gx = in();
  int gy = in();
  int N = in();

  for (int i = 0; i < N; ++i) {
    X[i] = in();
    Y[i] = in();
  }

  if (sx > gx) {
    sx = flip(sx);
    gx = flip(gx);
    for (int i = 0; i < N; ++i) {
      X[i] = flip(X[i]);
    }
  }
  if (sy > gy) {
    sy = flip(sy);
    gy = flip(gy);
    for (int i = 0; i < N; ++i) {
      Y[i] = flip(Y[i]);
    }
  }
  if (gx - sx < gy - sy) {
    swap(sx, sy);
    swap(gx, gy);
    for (int i = 0; i < N; ++i) {
      swap(X[i], Y[i]);
    }
  }

  map<int, int> xpos;
  for (int i = 0; i < N; ++i) {
    xpos[Y[i]] = X[i];
  }

  bool stairs = true;
  for (int y = sy, px = -1; y <= gy; ++y) {
    if (xpos.count(y) == 0) {
      stairs = false;
      break;
    }
    int x = xpos[y];
    if (px != -1 && x != px + 1) {
      stairs = false;
      break;
    }
    px = x;
  }

  if (stairs) {
    double res = 0;
    res += (5 * PI - 20) * (gy - sy);
    res += (10 * PI - 20);
    printf("%.13f\n", res + ((gx - sx) + (gy - sy)) * 100.0);
    return 0;
  }

  vector<pair<int, int>> F;
  for (int i = 0; i < N; ++i) {
    if (sy <= Y[i] && Y[i] <= gy && sx <= X[i] && X[i] <= gx) {
      F.emplace_back(Y[i], X[i]);
    }
  }
  sort(F.begin(), F.end());

  vector<int> xs;
  for (const auto& p : F) {
    xs.push_back(p.second);
  }

  int L = lis(xs);
  double res = (5 * PI - 20) * L;
  printf("%.13f\n", res + ((gx - sx) + (gy - sy)) * 100.0);

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:34:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘double fin()’:
./Main.cpp:35:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 double fin() { double x; scanf("%lf", &x); return x; }
                                          ^
./Main.cpp: In function ‘Int lin()’:
./Main.cpp:36:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 Int lin() { Int x; scanf("%lld", &x); return x; }
                                     ^

Judge Result