QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594673 | #9434. Italian Cuisine | ucup-team896# | WA | 32ms | 7192kb | C++23 | 9.5kb | 2024-09-28 09:33:25 | 2024-09-28 09:33:32 |
Judging History
answer
/* _ _ _ _ __ __ __
/ \ _ _ | |_ | |__ ___ _ __ _ ___ _ __ ___ | | __ / /_ / /_ / /_
/ _ \ | | | | | __| | '_ \ / _ \ | '__| (_) / __| | '_ ` _ \ | |/ / | '_ \ | '_ \ | '_ \
/ ___ \ | |_| | | |_ | | | | | (_) | | | _ | (__ | | | | | | | < | (_) | | (_) | | (_) |
/_/ \_\ \__,_| \__| |_| |_| \___/ |_| (_) \___| |_| |_| |_| |_|\_\ \___/ \___/ \___/
[Created Time: 2024-09-28 09:08:51]
[Last Modified Time: 2024-09-28 09:33:15] */
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include"debug.h"
#else
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
// ------------------------------
// #define DISABLE_MMAP
// ------------------------------
#if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifdef LOCAL
inline char _gc() { return getchar(); }
inline void _chk() {}
inline void _pc(char c) { putchar(c); }
inline void _pc_nochk(char c) { putchar(c); }
template < int n > inline void _pnc_nochk(const char *c) { for ( int i = 0 ; i < n ; i++ ) putchar(c[i]); }
#else
#ifdef DISABLE_MMAP
inline constexpr int _READ_SIZE = 1 << 18;
inline static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char _gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer, _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
}
return *_read_ptr++;
}
#else
#include<sys/mman.h>
inline static const char *_read_ptr = (const char *)mmap(nullptr, 0x7fffffff, 1, 2, 0, 0);
inline char _gc() { return *_read_ptr++; }
#endif
inline constexpr int _WRITE_SIZE = 1 << 18;
inline static char _write_buffer[_WRITE_SIZE + 40], *_write_ptr = _write_buffer;
inline void _chk()
{
if ( __builtin_expect(_write_buffer + _WRITE_SIZE <= _write_ptr, false) )
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout), _write_ptr = _write_buffer;
}
inline void _pc(char c) { *_write_ptr++ = c, _chk(); }
inline void _pc_nochk(char c) { *_write_ptr++ = c; }
template < int n > inline void _pnc_nochk(const char *c) { memcpy(_write_ptr, c, n), _write_ptr += n; }
inline struct _auto_flush
{
inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#define println println_ // don't use C++23 std::println
template < class T > inline constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T > inline constexpr bool _is_unsigned = numeric_limits < T >::is_integer && !_is_signed < T >;
#if __SIZEOF_LONG__ == 64
template <> inline constexpr bool _is_signed < __int128 > = true;
template <> inline constexpr bool _is_unsigned < __uint128_t > = true;
#endif
constexpr struct _table
{
char o[40000];
constexpr _table() : o{}
{
for ( int i = 0 ; i < 10000 ; i++ ) for ( int j = 3, k = i ; ~j ; j-- )
o[i * 4 + j] = ( k % 10 ) | 48, k /= 10;
}
} _table;
template < class T, int digit > inline constexpr T _pw10 = 10 * _pw10 < T, digit - 1 >;
template < class T > inline constexpr T _pw10 < T, 0 > = 1;
inline void read(char &c) { do c = _gc(); while ( !isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = _gc(); while ( !isgraph(c) ) c = _gc();
while ( isgraph(c) ) *s++ = c, c = _gc(); *s = 0;
}
inline void read(string &s)
{
char c = _gc(); s.clear(); while ( !isgraph(c) ) c = _gc();
while ( isgraph(c) ) s.push_back(c), c = _gc();
}
template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void read(T &x)
{
char c; bool f = true; while ( !isdigit(c = _gc()) ) if ( c == 45 ) f = false;
if ( f ) for ( x = c & 15 ; isdigit(c = _gc()) ; x = x * 10 + ( c & 15 ) );
else for ( x = -( c & 15 ) ; isdigit(c = _gc()) ; x = x * 10 - ( c & 15 ) );
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > inline void read(T &x)
{
char c; while ( !isdigit(c = _gc()) );
for ( x = c & 15 ; isdigit(c = _gc()) ; x = x * 10 + ( c & 15 ) );
}
inline void write(bool x) { _pc(x | 48); }
inline void write(char c) { _pc(c); }
inline void write_cstr(const char *s) { while ( *s ) _pc(*s++); }
inline void write(const string &s) { for ( char c : s ) _pc(c); }
template < class T, bool neg, int digit > inline void _write_int_suf(T x)
{
if constexpr ( digit == 4 ) _pnc_nochk < 4 >(_table.o + ( neg ? -x : x ) * 4);
else _write_int_suf < T, neg, digit / 2 >(x / _pw10 < T, digit / 2 >),
_write_int_suf < T, neg, digit / 2 >(x % _pw10 < T, digit / 2 >);
}
template < class T, bool neg, int digit > inline void _write_int_pre(T x)
{
if constexpr ( digit <= 4 )
if ( digit >= 3 && ( neg ? x <= -100 : x >= 100 ) )
if ( digit >= 4 && ( neg ? x <= -1000 : x >= 1000 ) )
_pnc_nochk < 4 >(_table.o + ( neg ? -x : x ) * 4 );
else _pnc_nochk < 3 >(_table.o + ( neg ? -x : x ) * 4 + 1);
else if ( digit >= 2 && ( neg ? x <= -10 : x >= 10 ) )
_pnc_nochk < 2 >(_table.o + ( neg ? -x : x ) * 4 + 2);
else _pc_nochk(( neg ? -x : x ) | 48);
else
{
constexpr int cur = 1 << __lg(digit - 1);
if ( neg ? x <= -_pw10 < T, cur > : x >= _pw10 < T, cur > )
_write_int_pre < T, neg, digit - cur >(x / _pw10 < T, cur >),
_write_int_suf < T, neg, cur >(x % _pw10 < T, cur >);
else _write_int_pre < T, neg, cur >(x );
}
}
template < class T, enable_if_t < _is_signed < T >, int > = 0 > inline void write(T x)
{
if ( x >= 0 ) _write_int_pre < T, false, numeric_limits < T >::digits10 + 1 >(x), _chk();
else _pc_nochk(45), _write_int_pre < T, true, numeric_limits < T >::digits10 + 1 >(x), _chk();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 > inline void write(T x)
{ _write_int_pre < T, false, numeric_limits < T >::digits10 + 1 >(x), _chk(); }
template < size_t N, class ...T > inline void _read_tuple(tuple < T... > &x)
{ read(get < N >(x)); if constexpr ( N + 1 != sizeof...(T) ) _read_tuple < N + 1, T... >(x); }
template < size_t N, class ...T > inline void _write_tuple(const tuple < T... > &x)
{ write(get < N >(x)); if constexpr ( N + 1 != sizeof...(T) ) _pc(32), _write_tuple < N + 1, T... >(x); }
template < class ...T > inline void read(tuple < T... > &x) { _read_tuple < 0, T... >(x); }
template < class ...T > inline void write(const tuple < T... > &x) { _write_tuple < 0, T... >(x); }
template < class T1, class T2 > inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 > inline void write(const pair < T1, T2 > &x) { write(x.first), _pc(32), write(x.second); }
template < class T1, class ...T2 > inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T > inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 > inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T > inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T > inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 > inline void print(const T1 &x, const T2 &...y) { write(x), _pc(32), print(y...); }
template < class ...T > inline void print_cstr(const char *x, const T *...y) { write_cstr(x), _pc(32), print_cstr(y...); }
inline void println() { _pc(10); } inline void println_cstr() { _pc(10); }
template < class ...T > inline void println(const T &...x) { print(x...), _pc(10); }
template < class ...T > inline void println_cstr(const T *...x) { print_cstr(x...), _pc(10); }
} using FastIO::read, FastIO::read_cstr, FastIO::write, FastIO::write_cstr, FastIO::println, FastIO::println_cstr;
using ld = long double; constexpr ld pi = numbers::pi_v < ld >;
struct P
{
int x, y;
inline P(int x = 0, int y = 0) : x(x), y(y) {}
inline P operator-(const P &z)const { return P(x - z.x, y - z.y); }
} c, a[200009];
inline __int128 sq(__int128 x) { return x * x; }
inline __int128 cr(const P &x, const P &y) { return (__int128)x.x * y.y - (__int128)x.y * y.x; }
inline __int128 dis(const P &x, const P &y) { return sq(x.x - y.x) + sq(x.y - y.y); }
inline ld ang(const P &x, const P &y) { return atan2l(y.y - x.y, y.x - x.x); }
int n, ra, l, r, md; ld gl, gr, gx; __int128 s[200009], ans;
inline bool chk(int x, int y)
{
gx = ang(a[x], a[y]);
if ( !( gl <= gr ? ( gl <= gx && gx <= gr ) : ( gl <= gx || gx <= gr ) ) ) return false;
return sq(cr(c - a[x], a[y] - a[x])) > dis(a[x], a[y]) * sq(ra);
}
inline void work()
{
read(n, c.x, c.y, ra), ans = 0;
For(i, 1, n) read(a[i].x, a[i].y), a[i + n] = a[i];
For(i, 2, n + n) s[i] = s[i - 1] + cr(a[i - 1], a[i]);
For(i, 1, n)
{
gl = ang(a[i], c), gr = gl < 0 ? gl + pi : gl - pi;
for ( l = i + 1, r = i + n - 1 ; l < r ; )
md = ( l + r ) >> 1, chk(i, md) ? r = md : l = md + 1;
ans = max(ans, s[i + n] - s[l] + cr(a[i], a[l]));
}
println(ans);
}
int main() { int t; read(t); For(tt, 1, t) work(); return 0; }
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7192kb
input:
3 5 1 1 1 0 0 1 0 5 0 3 3 0 5 6 2 4 1 2 0 4 0 6 3 4 6 2 6 0 3 4 3 3 1 3 0 6 3 3 6 0 3
output:
5 24 0
result:
ok 3 number(s): "5 24 0"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5828kb
input:
1 6 0 0 499999993 197878055 -535013568 696616963 -535013568 696616963 40162440 696616963 499999993 -499999993 499999993 -499999993 -535013568
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 32ms
memory: 6984kb
input:
6666 19 -142 -128 26 -172 -74 -188 -86 -199 -157 -200 -172 -199 -186 -195 -200 -175 -197 -161 -188 -144 -177 -127 -162 -107 -144 -90 -126 -87 -116 -86 -104 -89 -97 -108 -86 -125 -80 -142 -74 -162 -72 16 -161 -161 17 -165 -190 -157 -196 -154 -197 -144 -200 -132 -200 -128 -191 -120 -172 -123 -163 -138...
output:
5093 2862 2539 668 3535 7421 4883 5711 5624 1034 2479 3920 4372 2044 4996 5070 2251 4382 4175 1489 1154 3231 4038 1631 5086 14444 1692 6066 687 1512 4849 5456 2757 8341 8557 8235 1013 5203 10853 6042 6300 4480 2303 2728 1739 2187 3385 4266 6322 909 4334 1518 948 5036 1449 2376 3180 4810 1443 1786 47...
result:
wrong answer 2nd numbers differ - expected: '3086', found: '2862'