【JOI】情報オリンピック本選C問題解説 C - 最古の遺跡

こんにちは．

今日は2007年に行われた情報オリンピックの本選で出題された，C問題の最古の遺跡を解いたので解説していきます．

問題文

https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf#page=5

オンラインジャッジ(AtCoder) atcoder.jp

古代の街で座る男性

問題概要

かつての集落にあった神殿の記述がある． 神殿は上から見ると正方形であり，四隅には柱があった． 考古学者たちは遺跡から見つかった柱の中で正方形になっているもののうち，面積が最大のものが神殿に違いないと考えた．

柱の位置が座標平面上の点として個与えられるので，4本の柱でできる正方形のうち面積が最大のものの面積を出力せよ．

制約

考察

• ４つの点が与えられたら，正方形を作るかどうかの判定,正方形の面積の算出は でできる．

• しかし，n個の柱から4つを選ぶ方法は，通りもあり，およそ通りであるため，全探索していては間に合わない．

• 3つの点が与えられた場合，２つの点が与えられた場合を考えてみる．

• ３つの点が与えられた場合は，正方形を作るために必要な一点があるべき位置がわかるが，でもおよそ通りあるために間に合わない．

• 2つ点が与えられた場合，正方形を作るために必要な2点があるべき位置がわかり， 2点の組み合わせを全探索した場合はおよそであるため時間制限に間に合う．

• 2つの点が与えられた場合の残りの2点の位置候補はO(1)で求められる → で全探索できる！！

画像のように，2つの点A,Bが与えられた場合にC,Dが存在する場合や，E,Fが存在する場合には正方形を作ることができます．

2点と正方形を作るような点の図

, , , とすると，E,Fの座標を , , , と表すことができます．

実装

すべての点を受け取り，点が存在するかを配列でbool型にして記録しました．

C++コード例

#include <iostream>
#include <vector>
#include <map>

using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


vector<vector<bool>>is_there(5001, vector<bool>(5001));
bool find(pair<int,int> p){
    if (p.first > 5000 || p.second > 5000 or p.first < 0 or p.second < 0)return false;
    else return is_there[p.first][p.second];
}

int main() {
    int N;
    cin >> N;
    vector<pair<int,int> >xys(N);
    

    for (int i=0; i<N; i++){
        int xi, yi;
        cin >> xi >> yi;
        pair<int,int>p;
        p.first = xi;
        p.second = yi;
        is_there[p.first][p.second] = 1;
        xys[i] = p;
    }
    ll ans = 0;
    for (int i=0; i<N-1; i++){
        for (int j=i+1; j<N; j++){
            ll ax,ay,bx,by,dx,dy;
            ax = xys[i].first;
            ay = xys[i].second;
            bx = xys[j].first;
            by = xys[j].second;
            dx = bx-ax;
            dy = by-ay;

            pair<int,int> C, D, E, F;
            C.first = dy+ax;
            C.second = ax-dx;
            
            D.first = ax+dx+dy;
            D.second=ay+dy-dx;
            
            E.first=ax-dy;
            E.second=ay+dx;
            
            F.first=ax+dx-dy;
            F.second = ay+dx+dy;

            if ((find(C) and find(D)) or (find(E) and find(F))){
                chmax(ans, dx*dx + dy*dy);                  
            }
        }
    }
    cout << ans << endl;
}

まとめ

単純な全探索だと間に合わなくても，正方形という性質を利用することで探索する範囲を狭めることができる問題でした． JOI本選にしては簡単な問題に分類されるのではないでしょうか．

JOIなどではDPなどがよく出ますが，こういった工夫をして計算量を落とす問題を解けるようにすることで，力がつくのかもしれないですね．