D - Rectangles

・問題URL

https://atcoder.jp/contests/abc218/tasks/abc218_d

・発想

・4重ループは無理。
・3重ループに出きれば長方形は確定するのにと思ったが、対角線上の2
点決まれば長方形は確定。
・setに座標ぶち込んでいって、2重ループで所属判定すればギリ間に合いそう。どうだろ。

・解法

発想の通り。最後２で割るの忘れない(こーゆーのは忘れてもサンプル見れば気づくが)。二重ループとその中の所属判定がボトルネックでO(N²logN)
N≤4000より計算回数は定数部分も考慮すると最大で10⁸くらいか？。あぶない。解説がどれも難しいことやってるのはそのためか。まあ茶コーダーなら上等でしょう！
（Cより簡単やんけコラ～～～～！）

・コード

int main(){

 set<pair<ll,ll>>s;
 int N;
 cin>>N;
 vector<ll>x(N),y(N);
 rep(i,N){
   cin>>x[i]>>y[i];
   pair<ll,ll>P;
   P=make_pair(x[i],y[i]);
   s.insert(P);
 }
 
 ll ans=0;
 for(int i=0;i<N-1;i++){
   for(int j=i;j<N;j++){
     if(x[i]==x[j]||y[i]==y[j])continue;
     pair<ll,ll>Q,R;
     Q=make_pair(x[i],y[j]);
     R=make_pair(x[j],y[i]);
     if(s.count(Q)&&s.count(R))ans++;
   }
 }

 cout<<ans/2<<endl;

}