CS Academy #53 - Parallel Rectangles

問題

CS Academy

問題概要

xy平面に点が個与えられる。4点を選んで、それによって長方形を構成したいが、長方形のそれぞれの辺がx軸とy軸にそれぞれ平行になるようにしなければならない。 そのような4点の選び方は何通りあるか。

• 
• 

アイデア

1つ目の方針として、 を固定して、それ以外のに対して、それぞれのx座標でy座標が共通で存在するの点(とという意味)が個あるなら、通りの長方形を作れるということになる。これは、x座標の候補が多いと間に合わないのは明らか。

2つ目の方針としては、x座標を1つ固定する(とする)。そのx座標がのものに対して、y座標のペアをmapによって数え上げる(++map[(y1,y2)]みたいに)。すると、その各ペアに対して、通りの長方形を作れるということになる。しかし、これは同じx座標上に点があるとペアの数が大量になってmapが抱えるkeyの数が大きくなってしまう。

この2つの方針を組み合わせることを考える。同じx座標にある点の個数で各x座標を2つのタイプに分ける：

1. そのx座標に点が個より多く存在
2. そのx座標に点が個以下存在

すると、長方形としてx座標を2つ選んだ時、そのx座標のペアは

1. 両方がtype1
2. type1とtype2
3. 両方がtype2

のパターンに分類できる。パターン1と2は前者、3は後者で処理する。

前者に関しては、固定するはtype1のx座標のみを考える。すると、type1の性質により、この固定するはたかだか個になる。そして、この固定した1つのに対して、方針1はの時間がかかる。

後者に関しては、最悪の場合を考えると(個もつx座標が大量にある状況)、mapが抱えることになるのは個のkeyになる。

後者にはmapのlogが乗ることも考えると、はよりも小さくするのがバランスを取るためにはよい。今回はを採用した。色々いじってみたけどギリギリすぎる(自分のコードがダメなのかもしれない...)

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

const int N = 100001;
vector<int> X[N];

const int S = 70;

inline ll C2(ll n)
{
    return n*(n-1)/2;
}

int main()
{
    int n;
    cin >>n;
    vector<pi> p(n);
    rep(i,n) cin >>p[i].fi >>p[i].se;

    sort(all(p));

    rep(i,n) X[p[i].fi].pb(p[i].se);

    vector<int> can;
    rep(i,N)if(X[i].size()>=2) can.pb(i);

    ll ans = 0;

    map<pi,ll> ct;
    for(int x=1; x<N; ++x)
    {
        int SZ = X[x].size();
        if(SZ>S)
        {
            rep(i,can.size())if(x!=can[i])
            {
                int CAN_SZ = X[can[i]].size();
                if(CAN_SZ>S && can[i]>x) continue;

                int ii=0, xx=0;
                int cnt_y = 0;
                while(ii<CAN_SZ && xx<SZ)
                {
                    if(X[can[i]][ii] == X[x][xx])
                    {
                        ++cnt_y;
                        ++ii;
                        ++xx;
                    }
                    else if(X[can[i]][ii]>X[x][xx]) ++xx;
                    else ++ii;
                }

                ans += C2(cnt_y);
            }
        }
        else
        {
            rep(i,SZ)rep(j,i) ++ct[{X[x][j],X[x][i]}];
        }
    }

    for(const auto &t:ct) ans += C2(t.se);

    cout << ans << endl;
    return 0;
}