yukicoder No.202 1円玉投げ

問題

問題概要

円の中心座標が与えられる。円の半径は10cm。いくつの円をかなさならないようにおけるか。

解法

まず、Nが10⁵なので、円の中心が与えられてるたびに、過去に置いた円すべての中心間の距離を計算しておけるかどうかを確かめるとＯ(N*N)となり、TLEしてしまう。そこで考察として、円が重なる可能性のある円は、今おこうとしている円の中心を(cx,cy)とすると、重なる可能性のある円の中心のx座標はcx-20からcx+20、y座標はcy-20からcy+20の範囲にある円であるとわかる。次に、cxやcyの前後20の範囲にあるこれまでに置いた円の座標をどう取り出すか。今回の問題の制約はX,Yが小さいので、x座標やy座標でバケットソート的なことをした。center[i]に、x座標がiのy座標をいれることにした。そこから前後20にある円の中心座標を取り出してきて、中心間の距離を計算して20より小さければ置くことができないということになる。

ミス

はじめ、座標をvectorにいれて、毎回ソートして、2分探索して、前後20の座標を取り出していたけどTLE。

コード

AC

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

vector<int> center[20100];

int main(void){
    int n; cin >> n;
    int ans = 0;
    rep(i, n){
        int cx, cy; cin >> cx >> cy;
        int xl = max(0, cx - 20);
        int xr = cx + 20;
        bool flag = true;
        for (int nx = xl; nx <= xr; ++nx){
            for(auto ny : center[nx]){
                int len = (nx - cx) * (nx - cx) + (ny - cy) * (ny - cy);
                if(len < 400){//長さの二乗
                    flag = false;
                    break;
                }
            }
        }
        if(flag){
            ans++;
            center[cx].push_back(cy);
        }
    }

    printf("%d\n", ans);
    return 0;
}

TLE

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//TLE
int main(void){
    int n; cin >> n;
    vector<pair<int, int> > center;
    //(n^2*logn)でout?
    rep(i, n){
        int cx, cy; cin >> cx >> cy;
        if(center.size() != 0){
            sort(center.begin(), center.end());//(nlogn)
            int xl = cx - 20, xr = cx + 20;
            int yl = cy - 20, yr = cy + 20;
            //(logn)
            auto it1 = lower_bound(center.begin(), center.end(), make_pair(xl, yl));
            auto it2 = upper_bound(center.begin(), center.end(), make_pair(xr, yr));
            bool flag = true;
            //(n)
            for(auto itr = it1; itr != it2; ++itr) {
                auto p = *itr;
                int nx = p.first, ny = p.second;
                double len = sqrt((nx - cx) * (nx - cx) + (ny - cy) * (ny - cy));
                if(len < 20){
                    flag = false;
                    break;
                }
            }
            if(flag)center.push_back(make_pair(cx, cy));
        }else{
            center.push_back(make_pair(cx, cy));
        }
    }

    printf("%d\n", (int)center.size());
    return 0;
}