会津大学オンラインジャッジ 問

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A&lang=jp
平面上に散らばった１０万点から最も近い２地点を選ぶ問題。

ｘ、ｙ座標の順でソートして左から右へ平面走査をしていけばよいです。
素朴に実装したら何かメモリ使用量が大きくなりました。




#include<stdio.h>
#include<map>
#include<set>
#include<math.h>

struct P{
      double x,y;
      bool operator<(const P& p)const{
            return y<p.y;
      }
};

std::map<double ,std::set<double> > Ps;


int main(){
      P p;
      int n;
      double x,y;
      scanf("%d",&n);
      while(n--){
            scanf("%lf %lf",&x,&y);
            Ps[x].insert(y);
      }
      std::map<double ,std::set<double> >::iterator it;
      std::set<double>::iterator sItD,sItU;
      std::set<P> Left,Dells;
      std::set<P>::iterator pIt;
      double ans=1000000;
      for(it=Ps.begin();it!=Ps.end();){
            sItD=(*it).second.begin();
            sItU=sItD;
            sItU++;
            while(sItU!=(*it).second.end()){
                  double dy=fabs((*sItU)-(*sItD));
                  if(dy<ans)ans=dy;
                  sItU++;
                  sItD++;
            }
            sItD=(*it).second.begin();
            sItU=sItD;
            sItU++;
            double x=(*it).first;
            double dy,dx,dy2;
            Dells.clear();
            for(pIt=Left.begin();pIt!=Left.end();){
                  dy=fabs((*sItD)-(*pIt).y);
                  dx=fabs(x-(*pIt).x);
                  double len=hypot(dx,dy);
                  if(len<ans)ans=len;
                  if(dx>ans){
                        Dells.insert((*pIt));
                  }
                  if(sItU!=(*it).second.end()){
                        dy2=fabs((*sItU)-(*pIt).y);
                        if(dy2<dy){
                              sItD++;
                              sItU++;
                        }else{
                              pIt++;
                        }
                  }else{
                        pIt++;
                  }
            }
            for(pIt=Dells.begin();pIt!=Dells.end();pIt++){
                  Left.erase((*pIt));
            }
            for(sItD=(*it).second.begin();sItD!=(*it).second.end();sItD++){
                  p.x=x;
                  p.y=(*sItD);
                  Left.insert(p);
            }
            Ps.erase(x);
            it=Ps.begin();
      }
      printf("%0.7lf\n",ans);
}