v 0. Pasted by slipstak2 as cpp at 2011-01-11 14:14:47 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 14.
  2. // 14E. Поле для крикета [cricket]
  3. // O(N*N) для перебора угла +
  4. // O(N*logN) бинарный поиск длины + проверка корректности длины
  5. // ibelyaev: 10Jan2011
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <utility>
  10. #include <vector>
  11. #include <set>
  12.  
  13. using namespace std;
  14. #define X first
  15. #define Y second
  16. int n,W,H;
  17. vector<pair<int,int> > mas;
  18. set<int> XX,YY;
  19. void input()
  20. {
  21.     cin>>n>>W>>H;
  22.     mas.resize(n);
  23.     int x,y;
  24.     for (int i=0;i<n;i++) {
  25.         cin>>x>>y;
  26.         mas[i] = make_pair(x,y);
  27.         XX.insert(x); YY.insert(y);
  28.     }
  29.     mas.push_back(make_pair(0,0));
  30.     mas.push_back(make_pair(W,H));
  31.     n+=2;
  32.     XX.insert(0); XX.insert(W);
  33.     YY.insert(0); YY.insert(H);
  34. }
  35. void solve()
  36. {
  37.     int Xres, Yres, resLen = -1e9;
  38.     int curX, curY, curLen;
  39.     int xx,yy;
  40.     for (set<int>::iterator x = XX.begin(); x != XX.end(); x++) {
  41.         for (set<int>::iterator y = YY.begin(); y != YY.end(); y++) {
  42.            
  43.             int l = 0, r = 1e4 + 10;
  44.             while (l<=r) {
  45.                 int m = (l+r)>>1;
  46.                 int Xm = *x + m;
  47.                 int Ym = *y + m;
  48.                 if (Xm > W || Ym > H) {
  49.                     r = m - 1;
  50.                     continue;
  51.                 }
  52.                 bool isOK = false;
  53.                 for (int i=0;i<n;i++) {
  54.                     if (mas[i].X > *x && mas[i].Y > *y) {
  55.                         if (mas[i].X < Xm && mas[i].Y < Ym) {
  56.                             isOK = false;
  57.                             break;
  58.                         }
  59.                         else {
  60.                             isOK = true;
  61.                             xx = *x;
  62.                             yy = *y;
  63.                         }
  64.                     }
  65.                 }
  66.                 if (isOK){
  67.                     l = m + 1;
  68.                     curLen = m;
  69.                     curX = xx;
  70.                     curY = yy;
  71.                 }
  72.                 else
  73.                     r = m-1;
  74.             }
  75.             if (curLen > resLen) {
  76.                 resLen = curLen;
  77.                 Xres = curX;
  78.                 Yres = curY;
  79.             }
  80.         }
  81.     }
  82.     cout<<Xres<<' '<<Yres<<' '<<resLen;
  83. }
  84. int main()
  85. {
  86.     freopen("input.txt","r",stdin);
  87.     freopen("output.txt","w",stdout);
  88.  
  89.     input();
  90.     solve();
  91.     return 0;
  92. }


Editing is locked.