Submission #1542165
Source Code Expand
#pragma region Template
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <stack>
#include <set>
#include <algorithm>
#include <bitset>
#include <functional>
#include <ctime>
#include <cassert>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <complex>
#include <regex>
#include <numeric>
#pragma comment(linker, "/STACK:167772160")
using namespace std;
#define mp make_pair
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define print_var(x) cerr << #x << " : " << (x) << endl
#define print_array(arr, len) {cerr << #arr << " : "; for(int i = 0; i < len; ++i) cerr << arr[i] << ' '; cerr << endl;}
#define print_2d_array(arr, len1, len2) {cerr << #arr << endl; for(int i = 0; i < len1; ++i, cerr << endl) for(int j = 0; j < len2; ++j) cerr << arr[i][j] << ' ';}
#define print_iterable(i) {cerr << #i << " : "; for(auto e : i) cerr << e << ' '; cerr << endl;}
#define print_new_line() cerr << endl
template <typename T, typename Q>
void print_pair1(pair<T, Q> x)
{
cerr << "(" << x.first << ", " << x.second << ")\n";
}
#define print_pair(x) {cerr << #x << " : "; print_pair1(x);}
#else
#define print_pair(x) (void)0
#define eprintf(...) (void)0
#define print_var(x) (void)0
#define print_array(arr, len) {}
#define print_2d_array(arr, len1, len2) {}
#define print_iterable(i) {}
#define print_new_line() (void)0
#endif
#define rand govno_ebanoe
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = (int)1e9 + 10;
const ll LINF = ll(2e18) + 10;
const double PI = acosl(-1);
const double eps = 1e-8;
const ld EPS = 1e-12;
#pragma endregion
#ifdef LOCAL
#define ERR_CATCH
//#define NOERR
#endif
const int N = 2e5 + 10;
int n;
pll pts[N];
pll s, f;
vector<int> xs;
vector<int> ys;
struct Segt
{
int arr[4 * N];
Segt() : arr() {}
void add(int ind, int l, int r, int p, int v)
{
arr[ind] = max(arr[ind], v);
if (l == r)
return;
auto m = (l + r) / 2;
if (p <= m)
add(ind * 2, l, m, p, v);
else
add(ind * 2 + 1, m + 1, r, p, v);
}
void add(int p, int v)
{
add(1, 0, N - 1, p, v);
}
int get(int ind, int l, int r, int R)
{
if (r <= R)
return arr[ind];
if (R < l)
return 0;
auto m = (l + r) / 2;
return max(get(ind * 2, l, m, R), get(ind * 2 + 1, m + 1, r, R));
}
int get(int R)
{
return get(1, 0, N - 1, R);
}
} segt;
pll trans(pll p)
{
auto x = (ll)(lower_bound(xs.begin(), xs.end(), p.first) - xs.begin());
auto y = (ll)(lower_bound(ys.begin(), ys.end(), p.second) - ys.begin());
return { x, y };
}
void solve()
{
scanf("%lld%lld%lld%lld", &s.first, &s.second, &f.first, &f.second);
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%lld%lld", &pts[i].first, &pts[i].second);
if (s.first > f.first)
{
s.first = -s.first;
f.first = -f.first;
for (int i = 0; i < n; ++i)
pts[i].first = -pts[i].first;
}
if (s.second > f.second)
{
s.second = -s.second;
f.second = -f.second;
for (int i = 0; i < n; ++i)
pts[i].second = -pts[i].second;
}
double manh = (f.first - s.first + f.second - s.second) * 100;
auto n = f.first - s.first;
auto m = f.second - s.second;
if (s.first == f.first || s.second == f.second)
{
for (int i = 0; i < n; ++i)
if ((pts[i].first == s.first && pts[i].first == f.first && s.second <= pts[i].second && pts[i].second <= f.second) ||
(pts[i].second == s.second && pts[i].second == f.second && s.first <= pts[i].first && pts[i].first <= f.first))
{
printf("%.13lf\n", manh + 10 * (PI - 2));
return;
}
printf("%.13lf\n", manh);
return;
}
xs.push_back(s.first);
xs.push_back(f.first);
for (int i = 0; i < n; ++i)
xs.push_back(pts[i].first);
ys.push_back(s.second);
ys.push_back(f.second);
for (int i = 0; i < n; ++i)
ys.push_back(pts[i].second);
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
s = trans(s);
f = trans(f);
for (int i = 0; i < n; ++i)
pts[i] = trans(pts[i]);
sort(pts, pts + n);
int mx = 0;
for (int i = 0; i < n; ++i)
{
auto p = pts[i];
if (p.first < s.first || p.first > f.first || p.second < s.second || p.second > f.second)
continue;
auto cur = segt.get(p.second);
mx = max(mx, cur + 1);
segt.add(p.second, cur + 1);
}
print_var(mx);
print_var(manh);
if (mx == min(n, m) + 1)
manh += 10 * PI / 2;
printf("%.13lf\n", manh + mx * 10 * (PI / 2 - 2));
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef NOERR
freopen("err.txt", "w", stderr);
#endif
#else
//freopen("knight.in", "r", stdin);
//freopen("knight.out", "w", stdout);
#endif
#ifdef ERR_CATCH
try
{
#endif
#ifdef ST
while (true)
solve();
#endif
#ifdef CASES
#define MULTITEST
#endif
#ifdef MULTITEST
int t;
scanf("%d", &t);
char endl1[5];
fgets(endl1, 5, stdin);
for (int i = 0; i < t; ++i)
{
#ifdef CASES
printf("Case #%d: ", i + 1);
#endif
solve();
#ifdef CASES
eprintf("Passed case #%d:\n", i + 1);
#endif
}
#else
solve();
#endif
#ifdef ERR_CATCH
}
catch (logic_error e)
{
print_var(e.what());
puts("___________________________________________________________________________");
exit(0);
}
#endif
#ifdef LOCAL
eprintf("\n\nTime: %.3lf\n", double(clock()) / CLOCKS_PER_SEC);
#endif
}
Submission Info
Submission Time |
|
Task |
A - Ice Tea Store |
User |
tinsane |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5919 Byte |
Status |
WA |
Exec Time |
2104 ms |
Memory |
4480 KB |
Compile Error
./Main.cpp: In function ‘void solve()’:
./Main.cpp:129:69: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld", &s.first, &s.second, &f.first, &f.second);
^
./Main.cpp:130:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:132:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &pts[i].first, &pts[i].second);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.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 |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
WA |
3 ms |
4352 KB |
sample_02.txt |
WA |
3 ms |
4480 KB |
sample_03.txt |
WA |
2 ms |
4352 KB |
sample_04.txt |
TLE |
2104 ms |
4352 KB |
subtask_1_01.txt |
WA |
3 ms |
4352 KB |
subtask_1_02.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_03.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_04.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_05.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_06.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_07.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_08.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_09.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_10.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_11.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_12.txt |
TLE |
2104 ms |
4352 KB |
subtask_1_13.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_14.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_15.txt |
TLE |
2103 ms |
4352 KB |