Submission #6365754
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x) \
for(auto &youso_ : (x)) cin >> youso_
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
T x;
cin >> x;
return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
cin >> head;
CIN(move(tail)...);
}
#define CINT(...) \
int __VA_ARGS__; \
CIN(__VA_ARGS__)
#define DCIN(...) \
double __VA_ARGS__; \
CIN(__VA_ARGS__)
#define LCIN(...) \
ll __VA_ARGS__; \
CIN(__VA_ARGS__)
#define SCIN(...) \
string __VA_ARGS__; \
CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v) \
{ \
FOREACH(x, v) { cout << x << " "; } \
cout << "\n"; \
}
template <typename T = string> inline void eputs(T s) {
cout << s << "\n";
exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
std::fill((T *)array, (T *)(array + N), val);
}
template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;
typedef long long ll;
typedef unsigned long long ul;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double PI = atan(1.0) * 4.0;
// const int MOD = 998244353;
const ll LINF = 9e18;
const ll dx[] = {1, 0, -1, 0};
const ll dy[] = {0, 1, 0, -1};
void cinfast() {
cin.tie(0);
ios::sync_with_stdio(false);
}
const ll sup = 1e8;
vector<PL> F;
template <typename T = ll> vector<T> LIS(vector<T> v, T ini) {
ll n = v.size();
vector<T> ret(n, ini);
REP(i, n) { *lower_bound(All(ret), v[i]) = v[i]; }
ret.erase(lower_bound(All(ret), ini), ret.end());
return ret;
}
signed main() {
cinfast();
LCIN(x1, y1, x2, y2, N);
VL X(N), Y(N);
REP(i, N) cin >> X[i] >> Y[i];
if(x1 > x2) {
x1 = sup - x1;
x2 = sup - x2;
REP(i, N) X[i] = sup - X[i];
}
if(y1 > y2) {
y1 = sup - y1;
y2 = sup - y2;
REP(i, N) Y[i] = sup - Y[i];
}
REP(i, N) {
if(y1 <= Y[i] && Y[i] <= y2 && x1 <= X[i] && X[i] <= x2)
F.emplace_back(X[i], Y[i]);
}
sort(All(F));
VL ys;
REP(i, F.size()) ys.emplace_back(F[i].se);
auto lis = LIS<ll>(ys, LINF);
double ans = 100.0 * (x2 - x1 + y2 - y1);
ans += (5.0 * PI - 20.0) * lis.size();
if(lis.size() == min(x2 - x1, y2 - y1) + 1) ans += 5.0 * PI;
printf("%.15f\n", ans);
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
arktan763 |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
3838 Byte |
Status |
AC |
Exec Time |
68 ms |
Memory |
12780 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
1 ms |
256 KB |
subtask_1_04.txt |
AC |
1 ms |
256 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
AC |
1 ms |
256 KB |
subtask_1_07.txt |
AC |
1 ms |
256 KB |
subtask_1_08.txt |
AC |
1 ms |
256 KB |
subtask_1_09.txt |
AC |
14 ms |
1408 KB |
subtask_1_10.txt |
AC |
29 ms |
2560 KB |
subtask_1_11.txt |
AC |
8 ms |
896 KB |
subtask_1_12.txt |
AC |
68 ms |
12140 KB |
subtask_1_13.txt |
AC |
31 ms |
2688 KB |
subtask_1_14.txt |
AC |
15 ms |
1408 KB |
subtask_1_15.txt |
AC |
8 ms |
768 KB |
subtask_1_16.txt |
AC |
68 ms |
11756 KB |
subtask_1_17.txt |
AC |
26 ms |
2304 KB |
subtask_1_18.txt |
AC |
20 ms |
1792 KB |
subtask_1_19.txt |
AC |
20 ms |
1920 KB |
subtask_1_20.txt |
AC |
65 ms |
12780 KB |
subtask_1_21.txt |
AC |
67 ms |
11756 KB |
subtask_1_22.txt |
AC |
68 ms |
11756 KB |
subtask_1_23.txt |
AC |
68 ms |
11756 KB |
subtask_1_24.txt |
AC |
1 ms |
256 KB |
subtask_1_25.txt |
AC |
1 ms |
256 KB |
subtask_1_26.txt |
AC |
1 ms |
256 KB |
subtask_1_27.txt |
AC |
1 ms |
256 KB |
subtask_1_28.txt |
AC |
37 ms |
3712 KB |
subtask_1_29.txt |
AC |
40 ms |
3712 KB |
subtask_1_30.txt |
AC |
68 ms |
11756 KB |
subtask_1_31.txt |
AC |
45 ms |
11756 KB |
subtask_1_32.txt |
AC |
52 ms |
11756 KB |
subtask_1_33.txt |
AC |
51 ms |
11756 KB |
subtask_1_34.txt |
AC |
46 ms |
11756 KB |
subtask_1_35.txt |
AC |
56 ms |
11756 KB |
subtask_1_36.txt |
AC |
57 ms |
11756 KB |
subtask_1_37.txt |
AC |
56 ms |
11756 KB |
subtask_1_38.txt |
AC |
57 ms |
11756 KB |
subtask_1_39.txt |
AC |
56 ms |
12140 KB |
subtask_1_40.txt |
AC |
53 ms |
11756 KB |
subtask_1_41.txt |
AC |
53 ms |
11884 KB |