Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <cassert>
- using namespace std;
- typedef long long tint;
- #define forsn(i, s, n) for(int i=s;i<int(n);i++)
- #define forn(i, n) forsn(i, 0, n)
- #define all(v) v.begin(),v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define NACHO ios::sync_with_stdio(0); cin.tie(NULL);
- #define dbg cout << "hu" << endl;
- const tint INF = 11000000;
- const int MOD = 1000000007;
- int pinos[2001][2001];
- int frutas[2001][2001];
- int SP[2001][2001];
- int SF[2001][2001];
- int main(){
- NACHO;
- //ifstream cin("frutales.in");
- //ofstream cout("frutales.out");
- int n, m, p, f; cin >> n >> m >> p >> f;
- forn(i, p){
- int x, y; cin >> x >> y;
- pinos[x-1][y-1] = 1;
- }
- forn(i, f){
- int x, y; cin >> x >> y;
- frutas[x-1][y-1] = 1;
- }
- forsn(i, 1, n+1){
- forsn(j, 1, m+1){
- SP[i][j] = SP[i-1][j]+SP[i][j-1]-SP[i-1][j-1]+pinos[i-1][j-1];
- }
- }
- forsn(i, 1, n+1){
- forsn(j, 1, m+1){
- SF[i][j] = SF[i-1][j]+SF[i][j-1]-SF[i-1][j-1]+frutas[i-1][j-1];
- }
- }
- int posX = -1, posY = -1;
- int maxi = -1;
- int base = -1;
- forsn(i, 1, n+1){
- forsn(j, 1, m+1){
- int low = 0, high = min(n-i, m-j)+1;
- while(high-low > 1){
- int mid = (high+low)/2;
- if(SP[i+mid][j+mid]-SP[i-1][j+mid]-SP[i+mid][j-1]+SP[i-1][j-1] > 0) high = mid;
- else low = mid;
- }
- int low2 = 0, high2 = low;
- int act = SF[i+low][j+low]-SF[i-1][j+low]-SF[i+low][j-1]+SF[i-1][j-1];
- while(high2-low2 > 1){
- int mid = (low2+high2)/2;
- if(act == SF[i+mid][j+mid]-SF[i-1][j+mid]-SF[i+mid][j-1]+SF[i-1][j-1]){
- high2 = mid;
- }else low2 = mid;
- }
- if(act == maxi && high2 < base){
- base = high2+1;
- posX = i;
- posY = j;
- }else if(act > maxi){
- maxi = act;
- base = high2+1;
- posX = i;
- posY = j;
- }
- }
- }
- cout << posX-1 << " " << posY-1 << "\n";
- cout << base << "\n";
- cout << maxi << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement