SHOW:
|
|
- or go back to the newest paste.
| 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 (j=1; j<=n; j++) |
| 61 | + | for (i=1; i<=m; i++) |
| 62 | - | 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 | } |
