Решение задачи Поле для крикета с Меньшиков

Без пояснения   Просмотров: 21


Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложение своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.

Ваша задача - помочь бедному Архитектору сохранить голову, написав программу, которая найдёт максимальный размер поля для крикета и его положение внутри парка, удовлетворяющие требованиям Короля.

Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север - юг и восток - запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север - юг и восток - запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север - юг и восток - запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный - координаты (W, H), где W и H - длина и ширина парка соответственно.

В этой задаче вы можете пренебречь диаметром деревьев. Деревья не могут находиться внутри поля для крикета, но могут располагаться на его сторонах. Поле для крикета может также касаться границы парка, но не должно лежать вне парка.

Код

#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;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться