第６回日本情報オリンピック 本選 「最古の遺跡」

満点解法より効率の悪い解法を考えるほうが難しいと感じた。

• 部分点解法

４重ループで4本の柱を選び、それが正方形か調べその面積の最大値を求める。O(N).でもこんな解法を本気で考える人はいない気がするな・・・

• 満点解法

bool型の配列などで、座標を指定したらそこに柱があるのかすぐわかるようにする。そうすれば、正方形の２つの頂点を決定すればほかの２つも定まるのですぐに求められる。
計算量はだいたいO(N^2).

というか以前ブログにこの問題について書いてた↓

JOI本選過去問 第6回 日本情報オリンピック本選 3問目 最古の遺跡 - intさわだんのBlack History

また解き直したら前のブログの時より0.02secはやくなって笑った。

とりあえずささっと書き上げたので雑になってる気がする。すいません

#include <cstdio>

using namespace std;
bool ch[5001][5001];
int main(){
  
  while(1){
  
  int n,d[3002][2] = {0},ans = 0;
  
  
  scanf("%d",&n);
  
  if(n == 0)break;
  
  for(int i = 0;i < n;i++){
    scanf("%d%d",&d[i][0],&d[i][1]);
    ch[d[i][0]][d[i][1]] = true;
  }
  
  
  for(int i = 0;i < n;i++){
    for(int j = i + 1;j < n;j++){
      int x1 = d[i][0]; int y1 = d[i][1];
      int x2 = d[j][0]; int y2 = d[j][1];
      int po = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
      if(po <= ans) continue;
      int x3 = x2 + y2 - y1;
      int y3 = y2 + x1 - x2;
      if(x3 < 0 || x3 > 5000 || y3 < 0 || y3 > 5000 || ch[x3][y3] == false)continue;
      int x4 = x1 + y2 - y1;
      int y4 = y1 + x1 - x2;
      if(x4 >= 0 && x4 <= 5000 && y4 >= 0 && y4 <= 5000 & ch[x4][y4]){
	ans = po;
      }
    }
  }
  
  printf("%d\n",ans);
  }
      

  return 0;
}