Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2014
1,121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define MAX_INT 2147483647
  3. #define MAX_LONG 9223372036854775807ll
  4. #define MAX_ULONG 18446744073709551615ull
  5. #define MAX_DBL 1.7976931348623158e+308
  6. #define EPS 1e-9
  7. const double PI = 2.0*acos(0.0);
  8.  
  9. #define INF 1000000000
  10. //#define MOD 1000000007
  11. //#define MAXN N
  12.  
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair<int, int> ii;
  16.  
  17. int m, n, k, city[30005][1005], x, y, r, b, dis[30005], ans[1000005];
  18.  
  19. void update_ranges() {
  20.     int i, j, r2 = r*r, lim;
  21.     city[y][(x-r) >= 1 ? x-r : 1] += b;
  22.     if (x+r+1 <= n) city[y][x+r+1] -= b;
  23.    
  24.     lim = y+r-1;
  25.     for (i=y+1, j=0; i<=lim; i++, j++)
  26.         dis[j] = (int) sqrt(r2-(i-y)*(i-y));
  27.    
  28.     lim = min(m, y+r-1);
  29.     for (i=y+1, j=0; i<=lim; i++, j++) {
  30.         city[i][(x-dis[j]) >= 1 ? x-dis[j] : 1] += b;
  31.         if (x+dis[j]+1 <= n) city[i][x+dis[j]+1] -= b;
  32.     }
  33.     if ((y+r) <= m) {
  34.         city[y+r][x] += b;
  35.         if (x < n) city[y+r][x+1] -= b;
  36.     }
  37.     lim = max(0, y-r+1);
  38.     for (i=y-1, j=0; i>=lim; i--, j++) {
  39.         city[i][(x-dis[j]) >= 1 ? x-dis[j] : 1] += b;
  40.         if (x+dis[j]+1 <= n) city[i][x+dis[j]+1] -= b;
  41.     }
  42.     if ((y-r) >= 1) {
  43.         city[y-r][x] += b;
  44.         if (x < n) city[y-r][x+1] -= b;
  45.     }
  46. }
  47.  
  48. int main () {
  49.     ios_base::sync_with_stdio(0);
  50.     int i, j;
  51.    
  52.     scanf("%d", &m);
  53.     scanf("%d", &n);
  54.     scanf("%d", &k);
  55.    
  56.     for (i=0; i<k; i++) {
  57.         scanf("%d %d %d %d", &x, &y, &r, &b);
  58.         update_ranges();
  59.     }
  60.    
  61.     for (i=1; i<=m; i++)
  62.         for (j=1; j<=n; j++)
  63.             ans[city[i][j] += city[i][j-1]]++;
  64.    
  65.     for (i=1000005; ans[i]==0; i--);
  66.    
  67.     printf("%d\n%d\n", i, ans[i]);
  68.    
  69.     return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement