[JOI合宿]2008-Day1:Flu

愚直に探索するとN^2になりますが, 周辺の点を調べると計算が減る感じの幅優先探索問題です.
O2つけると爆速でいいですね.

ソートが一番重くて, O(NlogN)くらいだと思います.

整数点のユークリッド距離は二乗しておくと誤差が怖くないです.


C++力低すぎたのでコンストラクタと格闘していました. もうだめ.

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class Point {
    public:
    int x, y;
    int s, e;
    int idx;
    
    Point operator - (const Point &a)
    {
        Point t;
        t.x = x - a.x;
        t.y = y - a.y;
        return (t);
    }
};

int dist(Point p)
{
    return (p.x * p.x + p.y * p.y);
}

bool operator < (const Point &a, const Point &b){
    if (a.x - b.x){
        return (a.x < b.x);
    }
    return (a.y < b.y);
}

Point makePoint(int p, int q)
{
    Point t;
    t.x = p, t.y = q;
    t.e = t.s = -1;
    return (t);
}

int main()
{
    int n, m, d, k;
    vector<Point> p;
    Point st;
    
    scanf("%d %d %d %d", &n, &m, &d, &k);
    for (int i = 0; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        p.push_back(makePoint(a, b));
        if (i == 0){
            st = makePoint(a, b);
        }
    }
    
    sort(p.begin(), p.end());
    
    for (int i = 0; i < n; i++){
        p[i].idx = i;
        if (p[i].x == st.x && p[i].y == st.y){
            st.idx = i;
        }
    }
    
    queue<Point> q;
    
    bool v[100000];
    memset(v, 0, sizeof(v));
    v[st.idx] = 1;
    p[st.idx].s = 0, p[st.idx].e = m;
    
    q.push(p[st.idx]);
    
    while (!q.empty()){
        Point t = q.front(); q.pop();
        
        int pivot = t.idx;
        int ct;
        ct = 0;
        while (--pivot != -1 && t.x - p[pivot].x <= d){
            if (ct == 10) break;
            if (dist(t - p[pivot]) <= d * d){
                if (!v[pivot]){
                    v[pivot] = 1;
                    p[pivot].s = t.s + 1, p[pivot].e = t.e + 1;
                    q.push(p[pivot]);
                }
                ct++;
            }
        }
        
        pivot = t.idx;
        while (++pivot != n && p[pivot].x - t.x <= d){
            if (ct == 10) break;
            if (dist(t - p[pivot]) <= d * d){
                if (!v[pivot]){
                    v[pivot] = 1;
                    p[pivot].s = t.s + 1, p[pivot].e = t.e + 1;
                    q.push(p[pivot]);
                }
                ct++;
            }
        }
    }
    
    int res = 0;
    for (int i = 0; i < n; i++){
        if (p[i].s <= k && k < p[i].e) res++;
    }
    
    printf("%d\n", res);
    
    return (0);
}