SRM 331 div1 level 3

私は図形系問題が苦手なので苦労したが、1000点にしては比較的易しい部類だと思う。

解説はかなり短いがポイントは多い。

手順

1. 全ての「頂点候補」を洗い出す
2. 各「頂点候補」から右・下にそれぞれ辺を伸ばせる最大値を求めておく
3. 各「頂点候補」と同じY座標で右側にある全「頂点候補」に対して、その距離Lをもって以下のチェックする。
1. 起点となる「頂点候補」から距離L以上辺が右に伸ばせるか？
2. 起点となる「頂点候補」から距離L以上辺が下に伸ばせるか？
3. 同Y座標で右側の「頂点候補」から距離L以上辺が下に伸ばせるか？
4. 起点となる「頂点候補」と同じX座標で距離Lだけ下に「頂点候補」があるか？
5. ４の「頂点候補」から距離L以上辺が右に延ばせるか？
   
4. ３の全てがOKならばそれは正方形。
   

１で頂点を気にして考えると全ての線の交点を数えなければいけない気がするが、どの道後半で辺を伸ばせるかどうかチェックするので、実は頂点である必要はない。頂点となる候補であればよい。頂点のX座標はかならずx1,x2の配列の中にある。だから２つの配列x1,x2の重複を除いた全要素がxx頂点候補のX座標。同じくyyも求めると、xx.length × yy.length個の全(xx[i], yy[j])が頂点になりうる頂点候補である。勿論、全部が頂点ではない（全然違う点のX座標とY座標かもしれないが、気にしない）。

重複を除き、後の便利でソートするためにTreeSetを使っておく。andrewzta（Java）を参考にした。

２である点から右・下に伸ばせる辺の長さの最大を求めるにはプライベートクラスを作った。C++ではpairというクラスがあるらしくてうらやましいが。単にComparableをimplementsしてcompareToを実装するだけ。静的変数をみて何でソート対象変数・方向を切り替えることができるようにもできるので、自作Comparableクラス＋Arrays.sort()は便利である。

まず、四角の数だけi,x1[i],x2[i]のペアを作り、x1[i]の要素でソートする。x1順に並ぶわけである。それはつまり各辺が以下のように開始点順に並ぶわけである。点(x,y)から右に進める最大値を求めるには、全ペアをループしながら、添え字iからy1,y2を使ってY座標を調べ、y1かy2がyである辺を探す。それらの辺もやはり開始点順に並んでいるので、x1＜=x＜lx2である辺であれば、x=x2に進める。これを繰り返すと以下のように重なっている辺を渡り歩いて一番右まで進めるわけである。一番下まで進むにはこれをyで行う。全ての点について右最大値、下最大値を配列に覚えておく。

+======x
　　　+---=======x
　　　　+--o
　　　　　　　　　+---====X
　　　　　　　　　　　　　　　　　　+----o

あとは３で全頂点候補に関して、自分の右にある頂点候補に対して順にIF文を繰り返すだけである。全条件を満たせばカウンターをインクリメントし、それが 答えになる。

コード
public class HiddenSquares
{
 public int count(int[] x1, int[] y1, int[] x2, int[] y2)
 {
  int n = x1.length;
  Pair[] x = new Pair[n];
  Pair[] y = new Pair[n];
  TreeSet＜Integer＞ xx = new TreeSet＜Integer＞();
  TreeSet＜Integer＞ yy = new TreeSet＜Integer＞();
  for(int i=0;i＜n;i++){
   x[i] = new Pair(i, x1[i], x2[i]);
   y[i] = new Pair(i, y1[i], y2[i]);
   xx.add(x1[i]); xx.add(x2[i]);
   yy.add(y1[i]); yy.add(y2[i]);
  }
  Arrays.sort(x); Arrays.sort(y);
  int[] X = new int[xx.size()]; 
  int[] Y = new int[yy.size()];
  int idx=0;for(int a: xx) X[idx++]=a;
  idx=0;for(int a: yy) Y[idx++]=a;
  
  int[][] maxR = new int[X.length][Y.length];
  int[][] maxD = new int[X.length][Y.length];
  
  for(int i=0;i＜X.length;i++){
   for(int j=0;j＜Y.length;j++){
    // max Right
    int tx = X[i]; int ty = Y[j]; int start = tx;
    for(int k=0;k＜x.length;k++){
     if(y1[x[k].id] != ty && y2[x[k].id] != ty) continue;
     if(x[k].first ＜= start && x[k].second ＞ start){
      start = x[k].second;
     }
    }
    maxR[i][j] = start;
    // max Down
    start = ty;
    for(int k=0;k＜y.length;k++){
     if(x1[y[k].id] != tx && x2[y[k].id] != tx) continue;
     if(y[k].first ＜= start && y[k].second ＞ start) {
      start = y[k].second;
     }
    }
    maxD[i][j] = start;
   }
  }
  int count = 0;
  for(int i=0;i＜X.length;i++){
   for(int j=0;j＜Y.length;j++){
    int tx = X[i]; int ty = Y[j];
    for(int k=i+1;k＜X.length;k++){
     int rx = X[k];
     int L = rx-tx;
     if(maxR[i][j]-tx ＜ L) continue;
     if(maxD[i][j]-ty ＜ L) continue;
     if(maxD[k][j]-ty ＜ L) continue;
     // find bottom left corner
     int byindex = -1;
     for(int l=j+1;l＜Y.length && Y[l]＜=ty+L;l++){
      if(Y[l]==ty+L){byindex=l;break;}
     }
     if(byindex==-1) continue;
     if(maxR[i][byindex]-tx ＜ L) continue;
     count++;
    }
   }
  }
  return count;
 }
 
 class Pair implements Comparable {
  int id; int first; int second;
  public Pair(int id, int first, int second){
   this.id = id;
   this.first = first;
   this.second = second;
  }
  public int compareTo(Object o){
   Pair oo = (Pair)o;
   return this.first - oo.first;
  }
 }
}