QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594673#9434. Italian Cuisineucup-team896#WA 32ms7192kbC++239.5kb2024-09-28 09:33:252024-09-28 09:33:32

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 09:33:32]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:7192kb
  • [2024-09-28 09:33:25]
  • 提交

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'