fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. using pii = pair<int, int>;
  7. const int N = 2e3 + 5;
  8. int n, m;
  9. char c[N][N];
  10.  
  11. int a[N][N], ps[N][N];
  12. int nok[N][N];
  13. int Dx[] = {-1, 1, 0, 0};
  14. int Dy[] = {0, 0, -1, 1};
  15. inline int getRect(int x, int y, int u, int v) {
  16.     return ps[u][v] - ps[u][y - 1] - ps[x - 1][v] + ps[x - 1][y - 1];
  17. }
  18. inline int getNok(int x, int y, int u, int v) {
  19.     if (x > u || y > v) return 0;
  20.     return nok[u][v] - nok[u][y - 1] - nok[x - 1][v] + nok[x - 1][y - 1];
  21. }
  22.  
  23. inline pii ID(int x, int y) {
  24.     return {x + y - 1, x - y + m};
  25. }
  26. inline pii RID(int A, int B) {
  27.     int x = (A + B + 1 - m);
  28.     if (x & 1) return {-1, -1};
  29.     x /= 2;
  30.     int y = A - x + 1;
  31.     if (x < 1 || x > n || y < 1 || y > m) return {-1, -1};
  32.     return {x, y};
  33. }
  34.  
  35. signed main() {
  36.     cin.tie(NULL)->sync_with_stdio(false);
  37.     if(ifstream("RBULL.inp")) {
  38.         freopen("RBULL.inp", "r", stdin);
  39.         freopen("RBULL.out", "w", stdout);
  40.     }
  41.     cin >> n >> m;
  42.     for (int i = 1; i <= n; i++) {
  43.         for (int j = 1; j <= m; j++) {
  44.             cin >> c[i][j];
  45.         }
  46.     }
  47.     for (int i = 1; i <= n; i++) {
  48.         for (int j = 1; j <= m; j++) {
  49.             if (c[i][j] == '*') {
  50.                 a[i + j - 1][i - j + m] = 1;
  51.                 for (int mov = 0; mov < 4; mov++) {
  52.                     int tx = i + Dx[mov], ty = j + Dy[mov];
  53.                     if (!tx || !ty || tx >n || ty > m) continue;
  54.                     if (c[tx][ty] == '*') nok[i + j - 1][i - j + m] = 1;
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     for (int i = 1; i < n + m; i++) {
  60.         for (int j = 1; j < n + m; j++) {
  61.             ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i][j];
  62.             nok[i][j] = nok[i - 1][j] + nok[i][j - 1] - nok[i - 1][j - 1] + nok[i][j];
  63.         }
  64.     }
  65.     int ans = 0, ansX = 1, ansY = 1, ansR = 0;
  66.     for (int i = 1; i < n + m; i++) {
  67.         for (int j = 1; j < n + m; j++) {
  68.             pii tmp = RID(i, j); int x = tmp.ft, y = tmp.sc;
  69.             if (x == -1) continue;
  70.             int lo = 1, hi = min({x - 1, m - y, y - 1, (x - 1) / 2}), ansm = 0;
  71. //            cerr << i << " " << j << " min = " << hi << "\n";
  72.             while(lo <= hi) {
  73.                 int mid = lo + hi >> 1;
  74.                 if (getNok(i - mid * 2 + 1, j - mid * 2 + 1, i - 1, j - 1)) {
  75.                     hi = mid - 1;
  76.                 }
  77.                 else {
  78.                     ansm  = mid;
  79.                     lo = mid + 1;
  80.                 }
  81.             }
  82.             int val = getRect(i - ansm * 2, j - ansm * 2, i, j);
  83.             if (val > ans) {
  84.                 ans = val;
  85.                 ansR = ansm;
  86.                 pii tmp = RID(i - ansm, j - ansm);
  87.                 ansX = tmp.ft, ansY = tmp.sc;
  88. //                cerr << i << " " << j << " | " << x << " " << y << ": " << val << " -> " << ansm << " | " << ansX << " " << ansY << "\n";
  89.             }
  90.  
  91.         }
  92.     }
  93.  
  94.     if (ans == 0) return cout << "0 1 1 0", 0;
  95.     cout << ans << " " << ansX << " " << ansY << " " << ansR;
  96.  
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
0 1 1 0
https://ideone.com/o90CoZ
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!