CF #243 D TLE

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(LL k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(b-1); k >= (a); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))

typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<bool> VB;
typedef vector<pair<int,int> > VP;

int main()
{
#ifdef HOME
    clock_t startclock=clock();
    freopen ("in.txt","r",stdin);
    freopen ("out.txt","w",stdout);
    freopen ("out_err.txt","w",stderr);
#endif
    int n;
    scanf("%d",&n);
    vector<pair<int,int> > points(n);
    REP(i,n)
    {
        scanf("%d %d",&points[i].first,&points[i].second);
    }
    vector<pair<int,int> > p1=points;//x,y

    vector<pair<int,int> > p2=points;//y,x
    REP(i,n) swap(p2[i].first,p2[i].second);

    vector<pair<int,int> > pdiag=points;//x-y,x
    REP(i,n)
    {
        int x=points[i].first;
        int y=points[i].second;

        pdiag[i].first=x-y;
        pdiag[i].second=x;
    }

    sort(p1.begin(),p1.end());
    sort(p2.begin(),p2.end());
    sort(pdiag.begin(),pdiag.end());

    int res = 0;

    REP(i,n)
    {
        int actx = p1[i].first;
        int acty = p1[i].second;
        VP::iterator it1 = p1.begin()+i;
        VP::iterator it2 = find(p2.begin(),p2.end(),make_pair(acty,actx));
        VP::iterator it3 = find(pdiag.begin(),pdiag.end(),make_pair(actx-acty,actx));

        pair<int,int> pp;
        pp = make_pair(actx,1e6);
        VP::iterator endit1 = lower_bound(p1.begin(),p1.end(),pp);
        pp = make_pair(acty,1e6);
        VP::iterator endit2 = lower_bound(p2.begin(),p2.end(),pp);
        pp = make_pair(actx-acty,1e6);
        VP::iterator endit3 = lower_bound(pdiag.begin(),pdiag.end(),pp);
        ++it1,++it2,++it3;

        while(it1!=endit1 && it2!=endit2 && it3!=endit3)
        {
            if(it1->first>actx) break;
            if(it2->first>acty) break;
            if(it3->first>actx-acty) break;
            int k1 = it1->second-acty;
            int k2 = it2->second-actx;
            int k3 = it3->second-actx;

            int maxk = max(max(k1,k2),k3);
            bool ok = 1;
            pp = make_pair(actx,acty+maxk);
            it1 = lower_bound(it1, endit1,pp);
            if(it1 ==  endit1) break;
            if(*it1 != pp) ok=0;
            pp=make_pair(acty,actx+maxk);
            it2 = lower_bound(it2, endit2,pp);
            if(it2 ==  endit2) break;
            if(*it2 != pp) ok=0;
            pp=make_pair(actx-acty,actx+maxk);
            it3 = lower_bound(it3, endit3,pp);
            if(it3 == endit3) break;
            if(*it3 != pp) ok=0;
            if(ok)
            {
                ++it1,++it2,++it3;
                ++res;
            }
        }
    }

    printf("%d\n",res);

#ifdef HOME
    fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()-startclock));
#endif
    return 0;
}