ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209399 | #3713. 「盛夏!海岛?大冒险!」 | _Alexande_ | 100 | 11803ms | 502540kb | C++11 | 3.4kb | 2024-08-04 10:35:14 | 2024-08-04 12:38:57 |
answer
#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); ++ i )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); -- i )
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
char _c; bool _f; template < class type > inline void read ( type &x ) {
_f = 0, x = 0;
while ( _c = getchar (), !isdigit ( _c ) ) if ( _c == '-' ) _f = 1;
while ( isdigit ( _c ) ) x = x * 10 + _c - '0', _c = getchar (); if ( _f ) { x = -x; }
}
template < class type > inline void chkmin ( type &x, type y ) { x = ( x <= y ? x : y ); }
template < class type > inline void chkmax ( type &x, type y ) { x = ( x >= y ? x : y ); }
const int N = 1e5 + 5;
const int M = 4015;
int n, ans;
int pre1[M][M], pre2[M << 1][M << 1];
int p[4][M][M];
void add1 ( int x1, int y1, int x2, int y2 ) {
pre1[x1 + 2001][y1 + 2001] ++, pre1[x1 + 2001][y2 + 2001] --, pre1[x2 + 2001][y1 + 2001] --, pre1[x2 + 2001][y2 + 2001] ++;
}
void add2 ( int x1, int y1, int x2, int y2 ) {
pre2[x1 + 4002][y1 + 4002] ++, pre2[x1 + 4002][y2 + 4002] --, pre2[x2 + 4002][y1 + 4002] --, pre2[x2 + 4002][y2 + 4002] ++;
}
void Solve () {
ios :: sync_with_stdio ( false );
cin.tie ( 0 ), cout.tie ( 0 );
cin >> n;
for ( int i = 1; i <= n; i ++ ) {
int op, x, y, r;
cin >> op >> x >> y >> r;
r >>= 1;
if ( !op ) {
add1 ( x - r, y - r, x + r, y + r );
}
else {
int tmpx = x, tmpy = y;
x = tmpx + tmpy, y = tmpx - tmpy;
add2 ( x - r, y - r, x + r, y + r );
}
}
for ( int i = 0; i <= 4002; i ++ ) {
for ( int j = 0; j <= 4002; j ++ ) {
if ( !i && !j ) {
continue;
}
else if ( !i ) {
pre1[i][j] += pre1[i][j - 1];
}
else if ( !j ) {
pre1[i][j] += pre1[i - 1][j];
}
else {
pre1[i][j] += pre1[i - 1][j] + pre1[i][j - 1] - pre1[i - 1][j - 1];
}
}
}
for ( int i = 0; i <= 8004; i ++ ) {
for ( int j = 0; j <= 8004; j ++ ) {
if ( !i && !j ) {
continue;
}
else if ( !i ) {
pre2[i][j] += pre2[i][j - 1];
}
else if ( !j ) {
pre2[i][j] += pre2[i - 1][j];
}
else {
pre2[i][j] += pre2[i - 1][j] + pre2[i][j - 1] - pre2[i - 1][j - 1];
}
}
}
for ( int i = 0; i <= 4002; i ++ ) {
for ( int j = 0; j <= 4002; j ++ ) {
if ( pre1[i][j] ) {
p[0][i][j] = p[1][i][j] = p[2][i][j] = p[3][i][j] = 1;
}
}
}
for ( int i = 0; i <= 8004; i ++ ) {
for ( int j = 0; j <= 8004; j ++ ) {
if ( pre2[i][j] ) {
int tmpx = ( i + j ) >> 1, tmpy = ( i - j ) >> 1;
if ( i + j & 1 ) {
p[0][tmpx + 1 - 2001][( i - j - 1 ) / 2 + 2001] = p[1][tmpx - 2001][( i - j - 1 ) / 2 + 2001] = 1;
}
else {
p[2][tmpx - 2001][tmpy + 2001] = p[3][tmpx - 2001][tmpy + 2001 - 1] = 1;
}
}
}
}
for ( int i = 0; i <= 4002; i ++ ) {
for ( int j = 0; j <= 4002; j ++ ) {
ans += p[0][i][j] + p[1][i][j] + p[2][i][j] + p[3][i][j];
}
}
cout << fixed << setprecision ( 2 ) << ans / 4.0;
}
signed main () {
#ifdef judge
freopen ( "Code.in", "r", stdin );
freopen ( "Code.out", "w", stdout );
freopen ( "Code.err", "w", stderr );
#endif
Solve ();
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 368ms
memory: 501860kb
input:
77072 0 283 -138 88 0 946 -378 168 0 -86 721 716 0 160 -884 8 0 989 -112 20 0 930 555 938 0 -160 461...
output:
8881536.00
result:
ok single line: '8881536.00'
Test #2:
score: 0
Accepted
time: 361ms
memory: 502236kb
input:
96486 0 425 368 406 0 105 537 244 0 -255 -152 550 0 477 -204 598 0 -343 -138 94 0 -729 -150 952 0 37...
output:
8903707.00
result:
ok single line: '8903707.00'
Test #3:
score: 0
Accepted
time: 397ms
memory: 502136kb
input:
87587 0 87 -290 2 0 -426 -182 180 0 125 -137 182 0 -932 -88 240 0 144 30 62 0 688 351 972 0 -441 9 5...
output:
8897923.00
result:
ok single line: '8897923.00'
Test #4:
score: 0
Accepted
time: 393ms
memory: 502248kb
input:
98222 0 -958 472 548 0 440 476 398 0 289 733 880 0 -663 -515 480 0 14 448 312 0 366 606 92 0 -134 12...
output:
8906458.00
result:
ok single line: '8906458.00'
Test #5:
score: 0
Accepted
time: 447ms
memory: 501720kb
input:
76567 0 -93 -465 544 0 283 378 348 0 860 607 318 0 475 160 892 0 758 -362 94 0 -574 143 180 0 774 69...
output:
8880310.00
result:
ok single line: '8880310.00'
Test #6:
score: 0
Accepted
time: 509ms
memory: 502540kb
input:
97537 0 858 -639 232 0 551 -857 138 0 49 -760 438 0 847 -671 98 0 -580 -477 678 0 -974 -572 326 0 -1...
output:
8929243.00
result:
ok single line: '8929243.00'
Test #7:
score: 0
Accepted
time: 398ms
memory: 502276kb
input:
79171 0 -580 -543 606 0 -171 -151 372 0 281 371 234 0 -738 232 806 0 -859 -107 798 0 -559 -7 354 0 -...
output:
8906497.00
result:
ok single line: '8906497.00'
Test #8:
score: 0
Accepted
time: 385ms
memory: 501764kb
input:
98966 0 -248 784 28 0 162 697 970 0 663 360 784 0 291 -942 852 0 -221 569 400 0 492 4 876 0 159 -246...
output:
8879310.00
result:
ok single line: '8879310.00'
Test #9:
score: 0
Accepted
time: 390ms
memory: 502320kb
input:
92940 0 -732 -355 456 0 238 -444 208 0 -660 540 94 0 -799 -199 288 0 1000 -289 850 0 57 803 884 0 99...
output:
8909930.00
result:
ok single line: '8909930.00'
Test #10:
score: 0
Accepted
time: 394ms
memory: 501984kb
input:
93127 0 454 -304 858 0 -748 -141 874 0 962 991 54 0 -605 896 686 0 -567 570 364 0 389 -94 160 0 737 ...
output:
8898050.00
result:
ok single line: '8898050.00'
Subtask #2:
score: 70
Accepted
Test #11:
score: 70
Accepted
time: 854ms
memory: 501316kb
input:
83552 0 674 -510 126 0 -440 154 534 1 -761 -933 470 0 245 -674 798 1 776 566 420 0 -551 -112 958 1 -...
output:
8839013.00
result:
ok single line: '8839013.00'
Test #12:
score: 0
Accepted
time: 729ms
memory: 501212kb
input:
70752 0 552 532 706 0 185 595 76 0 122 624 612 1 -897 -880 804 0 960 -243 820 1 293 -949 596 0 -280 ...
output:
8842211.00
result:
ok single line: '8842211.00'
Test #13:
score: 0
Accepted
time: 850ms
memory: 491816kb
input:
92622 1 -413 -809 372 1 -81 42 394 1 154 -238 616 1 -779 195 498 1 -887 726 856 1 -309 776 304 1 -35...
output:
8130891.50
result:
ok single line: '8130891.50'
Test #14:
score: 0
Accepted
time: 786ms
memory: 501468kb
input:
70597 1 -543 894 546 0 621 109 384 1 -769 -81 382 0 -164 -522 728 0 589 -631 232 1 -515 547 216 0 -3...
output:
8857623.00
result:
ok single line: '8857623.00'
Test #15:
score: 0
Accepted
time: 811ms
memory: 500784kb
input:
79134 1 600 799 502 0 -920 -826 386 0 843 -528 610 1 -256 948 460 0 -213 573 92 1 -800 -445 498 0 93...
output:
8802739.00
result:
ok single line: '8802739.00'
Test #16:
score: 0
Accepted
time: 719ms
memory: 491672kb
input:
78421 1 -512 -91 56 1 -296 820 532 1 168 -497 636 1 -951 -142 680 1 402 35 994 1 673 -599 730 1 -593...
output:
8134084.50
result:
ok single line: '8134084.50'
Test #17:
score: 0
Accepted
time: 735ms
memory: 501912kb
input:
77922 0 523 -90 84 0 -62 866 614 1 274 -836 348 0 -673 -913 736 0 525 -490 248 0 350 -21 694 1 -123 ...
output:
8870242.50
result:
ok single line: '8870242.50'
Test #18:
score: 0
Accepted
time: 778ms
memory: 491360kb
input:
80055 1 612 -188 380 1 635 212 350 1 -398 512 520 1 371 902 318 1 537 982 910 1 -46 15 688 1 -910 -4...
output:
8118978.00
result:
ok single line: '8118978.00'
Test #19:
score: 0
Accepted
time: 738ms
memory: 501432kb
input:
84077 1 81 209 488 0 -773 -112 720 1 69 -435 854 0 -382 79 852 1 593 -96 600 1 -295 -395 432 1 -189 ...
output:
8842201.00
result:
ok single line: '8842201.00'
Test #20:
score: 0
Accepted
time: 761ms
memory: 491640kb
input:
96989 1 -47 -237 254 1 493 700 854 1 -52 515 436 1 823 -825 354 1 -996 -631 790 1 -169 -578 598 1 60...
output:
8137460.00
result:
ok single line: '8137460.00'
Extra Test:
score: 0
Extra Test Passed