JOI本選過去問 第6回 日本情報オリンピック本選 3問目 最古の遺跡

問題文はこちら

長年頭の中では解けていたけど、実装していなかった問題。

解けて頭がすっきりした。

解説の効率のよい解法で計算量がO(n^2 log n)と書いていたのをみて、「これはO(n^2/2)でいけるのでは」と思って実装してみた。

やるだけでとてもかんたんだけど。

intで座標管理したらMemory Limit Exceededになったのでboolにしたら通りました。

Public Solutions で(たぶん)はじめて実行時間一番短かったのでうれしい。（すぐぬかされるな）

↓↓↓

http://judge.u-aizu.ac.jp/onlinejudge/solution.jsp?pid=0518

#include <cstdio>
#include <string.h>

using namespace std;

int n = 0;

int d[3004][2] = {0};

bool za[5003][5003] = {0};



int main(){

  while(1){

    long ans = 0;

  memset(d,0,sizeof(d));

  memset(za,0,sizeof(za));

  scanf("%d",&n);

  if(n == 0) break;

  for(int i = 0;i < n;i++){
    scanf("%d%d",&d[i][0],&d[i][1]);
    za[d[i][1]][d[i][0]] = true;
  }

  for(int i = 0;i < n;i++){
    for(int j = 0;j < i;j++){

      int sy = d[i][1] - d[j][1];
      int sx = d[i][0] - d[j][0];

      if((sy*sy + sx*sx) <= ans) continue;

      int k1x = d[i][0] + sy;
      int k1y = d[i][1] - sx;

      int k2x = d[j][0] + sy;
      int k2y = d[j][1] - sx;

      if(k1x < 0 || k1x > 5000 || k1y < 0 || k1y > 5000 || k2x < 0 || k2x > 5000 || k2y < 0 || k2y > 5000){
	continue;
      }

      if(za[k1y][k1x] == true && za[k2y][k2x] == true){
	ans =  (sy*sy + sx*sx);
      }

    }
  }

  printf("%ld\n",ans);

  }

  return 0;

}

（解説よくみたらこんな感じでできるとも書いてました。。。