UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209392#3713. 「盛夏!海岛?大冒险!」_Alexande_10011897ms503180kbC++113.4kb2024-08-04 10:33:292024-08-04 12:38:10

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 + 2005][y1 + 2005] ++, pre1[x1 + 2005][y2 + 2005] --, pre1[x2 + 2005][y1 + 2005] --, pre1[x2 + 2005][y2 + 2005] ++;
}

void add2 ( int x1, int y1, int x2, int y2 ) {
  pre2[x1 + 4010][y1 + 4010] ++, pre2[x1 + 4010][y2 + 4010] --, pre2[x2 + 4010][y1 + 4010] --, pre2[x2 + 4010][y2 + 4010] ++;
}

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 <= 4010; i ++ ) {
    for ( int j = 0; j <= 4010; 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 <= 8020; i ++ ) {
    for ( int j = 0; j <= 8020; 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 <= 4010; i ++ ) {
    for ( int j = 0; j <= 4010; 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 <= 8020; i ++ ) {
    for ( int j = 0; j <= 8020; j ++ ) {
      if ( pre2[i][j] ) {
        int tmpx = ( i + j ) / 2, tmpy = ( i - j ) / 2;
        if ( i + j & 1 ) {
          p[0][tmpx + 1 - 2005][( i - j - 1 ) / 2 + 2005] = p[1][tmpx - 2005][( i - j - 1 ) / 2 + 2005] = 1;
        }
        else {
          p[2][tmpx - 2005][tmpy + 2005] = p[3][tmpx - 2005][tmpy + 2005 - 1] = 1;
        }
      }
    }
  }
  for ( int i = 0; i <= 4010; i ++ ) {
    for ( int j = 0; j <= 4010; 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;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 369ms
memory: 502512kb

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: 325ms
memory: 502864kb

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: 414ms
memory: 502752kb

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: 432ms
memory: 502900kb

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: 449ms
memory: 502340kb

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: 520ms
memory: 503180kb

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: 364ms
memory: 502904kb

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: 379ms
memory: 502420kb

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: 399ms
memory: 502928kb

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: 461ms
memory: 502640kb

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: 760ms
memory: 501948kb

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: 719ms
memory: 501848kb

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: 704ms
memory: 492456kb

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: 757ms
memory: 502112kb

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: 981ms
memory: 501400kb

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: 760ms
memory: 492288kb

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: 840ms
memory: 502512kb

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: 753ms
memory: 491984kb

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: 801ms
memory: 502028kb

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: 710ms
memory: 492288kb

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