Paste will expire never.
- // Меньшиков. Тренировка 14.
- // 14E. Поле для крикета [cricket]
- // O(N*N) для перебора угла +
- // O(N*logN) бинарный поиск длины + проверка корректности длины
- // ibelyaev: 10Jan2011
- #include <iostream>
- #include <cstdio>
- #include <utility>
- #include <vector>
- #include <set>
- using namespace std;
- #define X first
- #define Y second
- int n,W,H;
- vector<pair<int,int> > mas;
- set<int> XX,YY;
- void input()
- {
- cin>>n>>W>>H;
- mas.resize(n);
- int x,y;
- for (int i=0;i<n;i++) {
- cin>>x>>y;
- mas[i] = make_pair(x,y);
- XX.insert(x); YY.insert(y);
- }
- mas.push_back(make_pair(0,0));
- mas.push_back(make_pair(W,H));
- n+=2;
- XX.insert(0); XX.insert(W);
- YY.insert(0); YY.insert(H);
- }
- void solve()
- {
- int Xres, Yres, resLen = -1e9;
- int curX, curY, curLen;
- int xx,yy;
- for (set<int>::iterator x = XX.begin(); x != XX.end(); x++) {
- for (set<int>::iterator y = YY.begin(); y != YY.end(); y++) {
- int l = 0, r = 1e4 + 10;
- while (l<=r) {
- int m = (l+r)>>1;
- int Xm = *x + m;
- int Ym = *y + m;
- if (Xm > W || Ym > H) {
- r = m - 1;
- continue;
- }
- bool isOK = false;
- for (int i=0;i<n;i++) {
- if (mas[i].X > *x && mas[i].Y > *y) {
- if (mas[i].X < Xm && mas[i].Y < Ym) {
- isOK = false;
- break;
- }
- else {
- isOK = true;
- xx = *x;
- yy = *y;
- }
- }
- }
- if (isOK){
- l = m + 1;
- curLen = m;
- curX = xx;
- curY = yy;
- }
- else
- r = m-1;
- }
- if (curLen > resLen) {
- resLen = curLen;
- Xres = curX;
- Yres = curY;
- }
- }
- }
- cout<<Xres<<' '<<Yres<<' '<<resLen;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
Editing is locked.