Advertisement
Guest User

Untitled

a guest
Dec 14th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. using namespace std;
  5. struct park
  6. {
  7.     ll x1, y1, x2, y2;
  8. };;
  9. ll n, m, k, r, c, c1, c2, c3, c4, ans, ans1, ans2;
  10. park xp[105], yp[105];
  11. ll in(ll x11, ll x12, ll x21, ll x22)
  12. {
  13.     //cout << "sdf " << x11 << " " << x12 << " " << x21 << " " << x22 << "\n";
  14.     x11 = max(x11, x21);
  15.     x12 = min(x12, x22);
  16.     if(x12 - x11 + 1 >= 0)
  17.         return (x12 - x11 + 1);
  18.     return 0;
  19. }
  20. void inter(ll x1, ll y1, ll x2, ll y2)
  21. {
  22.     ll cur = 0;
  23.     if(x1 >= 1 && x1 <= n && x2 >= 1 && x2 <= n && y1 >= 1 && y1 <= m && y2 >= 1 && y2 <= m)
  24.     {
  25.         for(int i = 1; i <= k; i++)
  26.         {
  27.             cur += in(x1, x2, xp[i].x1, xp[i].x2) * in(y1, y2, xp[i].y1, xp[i].y2);
  28.         }
  29.         //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << cur << "\n";
  30.         if(cur < ans)
  31.         {
  32.             ans1 = x1;
  33.             ans2 = y1;
  34.             ans = cur;
  35.         }
  36.         if(cur == ans)
  37.         {
  38.             if(x1 < ans1)
  39.             {
  40.                 ans1 = x1;
  41.                 ans2 = y1;
  42.             }
  43.             if(x1 == ans1)
  44.             {
  45.                 if(y1 < ans2)
  46.                 {
  47.                     ans1 = x1;
  48.                     ans2 = y1;
  49.                 }
  50.             }
  51.         }
  52.     }
  53. }
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(0);
  57.     ifstream cin("input.txt");
  58.     ofstream cout("output.txt");
  59.     ans = 9999999999999;
  60.     cin >> n >> m >> k >> r >> c;
  61.     xp[0] = {0, 0, 0, m + 1};
  62.     xp[k + 1] = {n + 1, 0, n + 1, m + 1};
  63.     yp[0] = {1, 0, n, 0};
  64.     yp[k + 1] = {1, m + 1, n, m + 1};
  65.     for(int i = 1; i <= k; i++)
  66.     {
  67.         cin >> c1 >> c2 >> c3 >> c4;
  68.         yp[i] = xp[i] = {c1, c2, c3, c4};
  69.     }
  70.     for(int i = 0; i <= k + 1; i++)
  71.     {
  72.         for(int j = 0; j <= k + 1; j++)
  73.         {
  74.             ll x1 = 0, x2 = 0, y1 = 0, y2 = 0;
  75.             x2 = xp[i].x1 - 1;
  76.             x1 = x2 - r + 1;
  77.             y2 = yp[j].y1 - 1;
  78.             y1 = y2 - c + 1;
  79.             inter(x1, y1, x2, y2);
  80.             x1 = xp[i].x2 + 1;
  81.             x2 = x1 + r - 1;
  82.             y2 = yp[j].y1 - 1;
  83.             y1 = y2 - c + 1;
  84.             inter(x1, y1, x2, y2);
  85.             x2 = xp[i].x1 - 1;
  86.             x1 = x2 - r + 1;
  87.             y1 = yp[j].y2 + 1;
  88.             y2 = y1 + c - 1;
  89.             inter(x1, y1, x2, y2);
  90.             x1 = xp[i].x2 + 1;
  91.             x2 = x1 + r - 1;
  92.             y1 = yp[j].y2 + 1;
  93.             y2 = y1 + c - 1;
  94.             inter(x1, y1, x2, y2);
  95.         }
  96.     }
  97.     cout << ans1 << " " << ans2 << " " << ans;
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement