fork(1) download
  1. #pragma comment(linker, "/stack:20000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4.  
  5. #define _CRT_SECURE_NO_WARNINGS
  6. # include <iostream>
  7. # include <cmath>
  8. # include <algorithm>
  9. # include <stdio.h>
  10. # include <cstdint>
  11. # include <cstring>
  12. # include <string>
  13. # include <cstdlib>
  14. # include <vector>
  15. # include <bitset>
  16. # include <map>
  17. # include <queue>
  18. # include <ctime>
  19. # include <stack>
  20. # include <set>
  21. # include <list>
  22. # include <random>
  23. # include <deque>
  24. # include <functional>
  25. # include <iomanip>
  26. # include <sstream>
  27. # include <fstream>
  28. # include <complex>
  29. # include <numeric>
  30. # include <immintrin.h>
  31. # include <cassert>
  32. # include <array>
  33. # include <tuple>
  34.  
  35. //# include <opencv2/core/core.hpp>
  36. //# include <opencv2/highgui/highgui.hpp>
  37. //# include <opencv2/imgproc/imgproc.hpp>
  38.  
  39. using namespace std;
  40.  
  41. // Let's define unordered map
  42. # ifdef __GNUC__
  43. # if __cplusplus > 199711L
  44. # include <unordered_set>
  45. # include <unordered_map>
  46. # else
  47. # include <tr1/unordered_map>
  48. # include <tr1/unordered_set>
  49. using namespace tr1;
  50. # endif
  51. # else
  52. # include <unordered_map>
  53. # include <unordered_set>
  54. # endif
  55.  
  56. #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
  57. #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
  58. #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
  59. #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
  60. #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
  61. #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
  62. #define macro_dispatcher___(macro, nargs) macro ## nargs
  63. #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n"
  64. #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  65. #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  66. #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  67. #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
  68. #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
  69. #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
  70. #define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
  71. #define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
  72.  
  73. #ifdef _MSC_VER
  74. #define PREFETCH(ptr, rw, level) ((void)0)
  75. #else
  76. #define PREFETCH(ptr, rw, level) __builtin_prefetch(ptr, rw, level)
  77. #endif
  78.  
  79. #ifdef LOCAL
  80. #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
  81. #else
  82. #define CURTIME()
  83. #endif
  84.  
  85. #define mp make_pair
  86. typedef long long ll;
  87. typedef unsigned int uint;
  88. typedef unsigned long long ull;
  89. typedef pair<int, int> pii;
  90. typedef pair<long long, long long> pll;
  91. typedef vector<int> vi;
  92. typedef vector<long long> vll;
  93. typedef int itn;
  94.  
  95. template<class T1, class T2, class T3>
  96. struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
  97. template<class T1, class T2, class T3>
  98. bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
  99. template<class T1, class T2, class T3>
  100. bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
  101. #define tri triple<int,int,int>
  102. #define trll triple<ll,ll,ll>
  103.  
  104. #define FI(n) for(int i=0;i<(n);++i)
  105. #define FJ(n) for(int j=0;j<(n);++j)
  106. #define FK(n) for(int k=0;k<(n);++k)
  107. #define FL(n) for(int l=0;l<(n);++l)
  108. #define FQ(n) for(int q=0;q<(n);++q)
  109. #define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
  110. #define all(a) std::begin(a), std::end(a)
  111. #define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
  112.  
  113. #define sqr(x) ((x) * (x))
  114. #define sqrt(x) sqrt(1.0 * (x))
  115. #define pow(x, n) pow(1.0 * (x), n)
  116.  
  117. #define COMPARE(obj) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b)
  118. #define COMPARE_BY(obj, field) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b) { return a.field < b.field; }
  119.  
  120. #define checkbit(n, b) (((n) >> (b)) & 1)
  121. #define setbit(n, b) ((n) | (static_cast<std::decay_t<decltype(n)>>(1) << (b)))
  122. #define removebit(n, b) ((n) & ~(static_cast<std::decay_t<decltype(n)>>(1) << (b)))
  123. #define flipbit(n, b) ((n) ^ (static_cast<std::decay_t<decltype(n)>>(1) << (b)))
  124. inline int countBits(uint v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
  125. inline int countBits(ull v){uint t=v>>32;uint p=(v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
  126. inline int countBits(ll v){return countBits((ull)v); }
  127. inline int countBits(int v){return countBits((uint)v); }
  128. unsigned int reverseBits(uint x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
  129. template<class T> inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
  130. inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
  131. constexpr ll power(ll x, int p) { return p == 0 ? 1 : (x * power(x, p - 1)); }
  132. template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
  133. unsigned long long rdtsc() { unsigned long long ret = 0;
  134. #ifdef __clang__
  135. return __builtin_readcyclecounter();
  136. #endif
  137. #ifndef _MSC_VER
  138. asm volatile("rdtsc" : "=A" (ret) : :);
  139. #endif
  140. return ret; }
  141. // Fast IO ********************************************************************************************************
  142. const int __BS = 4096;
  143. static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
  144. template<class T = int> T readInt() {
  145. auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  146. c(); while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir; c();
  147. bool m = false; if (*__ir == '-') ++__ir, c(), m = true;
  148. T r = 0; while (*__ir >= '0' && *__ir <= '9') r = r * 10 + *__ir - '0', ++__ir, c();
  149. ++__ir; return m ? -r : r;
  150. }
  151. static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
  152. template<class T>
  153. void writeInt(T x, char endc = '\n') {
  154. if (x < 0) *__iw++ = '-', x = -x; if (x == 0) *__iw++ = '0';
  155. char* s = __iw;
  156. while (x) { T t = x / 10; char c = x - 10 * t + '0'; *__iw++ = c; x = t; }
  157. char* f = __iw - 1; while (s < f) swap(*s, *f), ++s, --f;
  158. if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
  159. *__iw++ = endc;
  160. }
  161. template<class T>
  162. void writeStr(const T& str) {
  163. int i = 0; while (str[i]) { *__iw++ = str[i++]; if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw; }
  164. }
  165. struct __FL__ { ~__FL__() { if (__iw != __buw) cout.write(__buw, __iw - __buw); } };
  166. static __FL__ __flushVar__;
  167.  
  168. //STL output *****************************************************************************************************
  169. #define TT1 template<class T>
  170. #define TT1T2 template<class T1, class T2>
  171. #define TT1T2T3 template<class T1, class T2, class T3>
  172. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
  173. TT1 ostream& operator << (ostream& os, const vector<T>& v);
  174. TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
  175. TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
  176. TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
  177. TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
  178. TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
  179. TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
  180. template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v);
  181. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
  182. TT1 ostream& operator << (ostream& os, const vector<T>& v){ bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  183. template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v) { bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  184. TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){ bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  185. TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  186. TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  187. TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  188. TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
  189. TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
  190. TT1T2 void printarray(const T1& a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  191.  
  192. //STL input *****************************************************************************************************
  193. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
  194. TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
  195. TT1 inline istream& operator >> (istream& os, vector<T>& v) {
  196. if (v.size()) for (T& t : v) os >> t; else {
  197. string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
  198. stringstream ss(s); while (ss >> obj) v.push_back(obj);
  199. }
  200. return os;
  201. }
  202. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
  203.  
  204. //Pair magic *****************************************************************************************************
  205. #define PT1T2 pair<T1, T2>
  206. TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
  207. TT1T2 inline PT1T2& operator+=(PT1T2 &p1 , const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
  208. TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
  209. TT1T2 inline PT1T2& operator-=(PT1T2 &p1 , const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
  210.  
  211. #undef TT1
  212. #undef TT1T2
  213. #undef TT1T2T3
  214.  
  215. #define FREIN(FILE) freopen(FILE, "rt", stdin)
  216. #define FREOUT(FILE) freopen(FILE, "wt", stdout)
  217. #ifdef LOCAL
  218. #define BEGIN_PROFILE(idx, name) int profileIdx = idx; profileName[profileIdx] = name; totalTime[profileIdx] -= rdtsc() / 1e3;
  219. #define END_PROFILE totalTime[profileIdx] += rdtsc() / 1e3; totalCount[profileIdx]++;
  220. #else
  221. #define BEGIN_PROFILE(idx, name)
  222. #define END_PROFILE
  223. #endif
  224.  
  225. template<class T> inline void normmod(T &x, T m) { x %= m; if (x < 0) x += m; }
  226. template<class T1, class T2> inline T2 summodfast(T1 x, T1 y, T2 m) { T2 res = x + y; if (res >= m) res -= m; return res; }
  227. template<class T1, class T2, class T3> inline void addmodfast(T1 &x, T2 y, T3 m) { x += y; if (x >= m) x -= m; }
  228. template<class T1, class T2, class T3> inline void submodfast(T1 &x, T2 y, T3 m) { x -= y; if (x < 0) x += m; }
  229. #if INTPTR_MAX == INT32_MAX or !defined(__SIZEOF_INT128__)
  230. inline ll mulmod(ll x, ll n, ll m){ ll r = 0; normmod(x, m); normmod(n, m); while (n) { if (n & 1) r += x; x += x; if (r >= m) r -= m; if (x >= m) x -= m; n /= 2; } return r; }
  231. #else
  232. using int128 = __int128;
  233. inline ll mulmod(ll x, ll n, ll m){ return __int128(x) * n % m; }
  234. #endif
  235. inline ll powmod(ll x, ll n, ll m){ ll r = 1; normmod(x, m); while (n){ if (n & 1)r = (r*x) % m; x = (x*x) % m; n /= 2; }return r; }
  236. inline ll powmulmod(ll x, ll n, ll m) { ll res = 1; normmod(x, m); while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n /= 2; } return res; }
  237. template<class T> inline T gcd(T a, T b) { while (b) { a %= b; T t = a; a = b; b = t; } return a; }
  238. inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
  239. template<class T> inline T gcd(T a, T b, T c){ return gcd(gcd(a, b), c); }
  240. ll gcdex(ll a, ll b, ll& x, ll& y) {
  241. if (!a) { x = 0; y = 1; return b; }
  242. ll y1; ll d = gcdex(b % a, a, y, y1); x = y1 - (b / a) * y;
  243. return d;
  244. }
  245. template<class T> bool isPrime(T x) { if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  246. for (T i = 5; i * i <= x; i += 6) if (x % i == 0 || x % (i + 2) == 0) return 0; return 1; }
  247. bool millerRabin(long long n) {
  248. if (n <= 1000) return isPrime(n);
  249. long long s = n - 1; int t = 0; while (s % 2 == 0) s /= 2, ++t;
  250. for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if (!(a %= n)) return true;
  251. long long f = powmulmod(a, s, n); if (f == 1 || f == n - 1) continue;
  252. for (int i = 1; i < t; ++i) if ((f = mulmod(f, f, n)) == n - 1) goto nextp;
  253. return false; nextp:;
  254. } return true;
  255. }
  256.  
  257. // Useful constants
  258.  
  259. //int some_primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431, 1000000123};
  260. #define T9 1000000000
  261. #define T18 1000000000000000000LL
  262. #define INF 1011111111
  263. #define LLINF 1000111000111000111LL
  264. #define mod 1000000007
  265. #define EPS (double)1e-10
  266. #define PI 3.14159265358979323846264
  267. #define link asaxlajrewqwe
  268. #define rank wahayawehasdakw
  269. //*************************************************************************************
  270.  
  271. int32_t solve();
  272. int32_t main(int argc, char** argv) {
  273. ios_base::sync_with_stdio(0);cin.tie(0);
  274. #ifdef LOCAL
  275. // FREIN("input.txt");
  276. // FREOUT("out.txt");
  277. #endif
  278. return solve();
  279. }
  280.  
  281. const int N = 4050;
  282. int ps1[N][N];
  283. using T = decltype(ps1);
  284. T rd, ld, lu, ru;
  285.  
  286. int solve() {
  287. int n;
  288. cin >> n;
  289. FI(n) {
  290. char c;
  291. cin >> c;
  292. int x, y, z;
  293. cin >> x >> y >> z;
  294. x += 2002;
  295. y += 2002;
  296. if (c == 'A') {
  297. x += z / 2;
  298. y += z / 2;
  299. ps1[x][y]++;
  300. ps1[x][y - z]--;
  301. ps1[x - z][y]--;
  302. ps1[x - z][y - z]++;
  303. } else {
  304. rd[x + z / 2][y]++;
  305. rd[x][y + z / 2]--;
  306. rd[x][y - z / 2]--;
  307. rd[x - z / 2][y]++;
  308.  
  309. rd[x + z / 2 - 1][y]++;
  310. rd[x - 1][y + z / 2]--;
  311. rd[x][y - z / 2 + 1]--;
  312. rd[x - z / 2][y + 1]++;
  313.  
  314. ld[x + z / 2][y + 1]++;
  315. ld[x][y - z / 2 + 1]--;
  316. ld[x][y + z / 2 + 1]--;
  317. ld[x - z / 2][y + 1]++;
  318.  
  319. ld[x + z / 2 - 1][y + 1]++;
  320. ld[x][y + z / 2]--;
  321. ld[x - 1][y - z / 2 + 1]--;
  322. ld[x - z / 2][y]++;
  323.  
  324. lu[x + z / 2 - 1][y]++;
  325. lu[x][y - z / 2 + 1]--;
  326. lu[x - 1][y + z / 2]--;
  327. lu[x - z / 2][y + 1]++;
  328.  
  329. lu[x + z / 2 - 1][y + 1]++;
  330. lu[x - 1][y + z / 2 + 1]--;
  331. lu[x - 1][y - z / 2 + 1]--;
  332. lu[x - z / 2 - 1][y + 1]++;
  333.  
  334. ru[x + z / 2 - 1][y]++;
  335. ru[x - 1][y - z / 2]--;
  336. ru[x - 1][y + z / 2]--;
  337. ru[x - z / 2 - 1][y]++;
  338.  
  339. ru[x + z / 2 - 1][y + 1]++;
  340. ru[x][y + z / 2]--;
  341. ru[x - 1][y - z / 2 + 1]--;
  342. ru[x - z / 2][y]++;
  343. }
  344. }
  345. void* ptrs[4] = {lu, ld, ru, rd};
  346. for (int i = 4004; i >= 0; --i) {
  347. for (int j = 1; j <= 4004; ++j) {
  348. for (auto ptr : ptrs) {
  349. auto p = (int(*)[N])ptr;
  350. p[i][j] += p[i + 1][j - 1] + p[i + 1][j + 1] - p[i + 2][j];
  351. }
  352. }
  353. }
  354. for (int i = 4004; i >= 0; --i) {
  355. for (int j = 4004; j >= 0; --j) {
  356. ps1[i][j] += ps1[i + 1][j] + ps1[i][j + 1] - ps1[i + 1][j + 1];
  357. }
  358. }
  359. int ans = 0;
  360. for (int i = 4004; i >= 0; --i) {
  361. for (int j = 4004; j >= 0; --j) {
  362. int t = (ps1[i][j] != 0) * 15;
  363. if (lu[i][j]) t |= 1 | 2;
  364. if (ru[i][j]) t |= 2 | 4;
  365. if (rd[i][j]) t |= 4 | 8;
  366. if (ld[i][j]) t |= 8 | 1;
  367. ans += countBits(t);
  368. }
  369. }
  370. cout << fixed;
  371. cout.precision(10);
  372. int ost = ans % 4;
  373. cout << ans / 4;
  374. if (ost == 0) {
  375. cout << ".00" << endl;
  376. } else if (ost == 1) {
  377. cout << ".25" << endl;
  378. } else if (ost == 2) {
  379. cout << ".50" << endl;
  380. } else {
  381. cout << ".75" << endl;
  382. }
  383. return 0;
  384. }
  385.  
  386.  
Success #stdin #stdout 0.21s 335616KB
stdin
8
A -7 10 4
B 3 10 8
A -6 6 6
A -2 5 8
B 3 -1 8
B -7 -4 8
A 3 9 2
B 8 6 6
stdout
205.50