Submission #30518

---

Source Code Expand

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

template <class T>
class myset {
    public:

    myset()
    {
        top = NULL;
    }
    
    ~myset()
    {
        clear(top);
    }
    
    bool empty(void)
    {
        if (top == NULL) {
            return true;
        } else {
            return false;
        }
    }
    
    int size(void)
    {
        return size(top);
    }
    
    void insert(T key)
    {
        top = insert(top, key);
    }
    
    void erase(T key)
    {
        top = erase(top, key);
    }
    
    int find(T key)
    {
        int tmp = find(top, key);
        
        if (tmp == -1) tmp = size(top);
        
        return tmp;
    }
    
    int count(T key)
    {
        return count(top, key);
    }
    
    void clear(void)
    {
        clear(top);
        top = NULL;
    }
    
    T rank(int n)
    {
        return rank(top, n);
    }
    
    int lower_bound(T key)
    {
        int tmp = lower_bound(top, key);
        
        if (tmp == -1) tmp = size(top);
        
        return tmp;
    }
    
    int upper_bound(T key)
    {
        int tmp = upper_bound(top, key);
        
        if (tmp == -1) tmp = size(top);
        
        return tmp;
    }
    
    private:
    
    typedef struct _myset {
        T key;
        int size;
        int height;
        struct _myset *child[2];
    } _myset;
    
    _myset *top;
    
    int size(_myset *s)
    {
        if (s == NULL) {
            return 0;
        } else {
            return s->size;
        }
    }
    
    int height(_myset *s)
    {
        if (s == NULL) {
            return 0;
        } else {
            return s->height;
        }
    }
    
    _myset *balance(_myset *s)
    {
        for (int i = 0; i < 2; i++) {
            if (height(s->child[!i]) - height(s->child[i]) < -1) {
                if (height(s->child[i]->child[!i]) - height(s->child[i]->child[i]) > 0) {
                    s->child[i] = rotate(s->child[i], i, !i);
                }
                
                return rotate(s, !i, i);
            }
        }
        
        if (s != NULL) {
            if (height(s->child[0]) > height(s->child[1])) {
                s->height = height(s->child[0]) + 1;
            } else {
                s->height = height(s->child[1]) + 1;
            }
            
            s->size = size(s->child[0]) + size(s->child[1]) + 1;
        }
        
        return s;
    }
    
    _myset *rotate(_myset *s, int l, int r)
    {
        _myset *t = s->child[r];
        
        s->child[r] = t->child[l];
        t->child[l] = balance(s);
        
        if (s != NULL) s->size = size(s->child[0]) + size(s->child[1]) + 1;
        if (t != NULL) t->size = size(t->child[0]) + size(t->child[1]) + 1;
        
        return balance(t);
    }
    
    _myset *insert(_myset *s, T key)
    {
        if (s == NULL) {
            _myset *tmp = new _myset;
            
            tmp->key = key;
            tmp->size = 1;
            tmp->height = 1;
            tmp->child[0] = NULL;
            tmp->child[1] = NULL;
            
            return tmp;
        }
        
        if (key < s->key) {
            s->child[0] = insert(s->child[0], key);
        } else if (key == s->key) {
            return s;
        } else {
            s->child[1] = insert(s->child[1], key);
        }
        
        s->size++;
        
        return balance(s);
    }
    
    _myset *move_down(_myset *s, _myset *t)
    {
        if (s == NULL) return t;
        
        s->child[1] = move_down(s->child[1], t);
        
        return balance(s);
    }
    
    _myset *erase(_myset *s, T key)
    {
        if (s == NULL) return NULL;
        
        if (key < s->key) {
            s->child[0] = erase(s->child[0], key);
        } else if (key == s->key) {
            _myset *tmp = move_down(s->child[0], s->child[1]);
            
            delete s;
            
            return tmp;
        } else {
            s->child[1] = erase(s->child[1], key);
        }
        
        s->size--;
        
        return balance(s);
    }
    
    int find(_myset *s, T key)
    {
        if (s == NULL) return -1;
        
        if (key < s->key) {
            return find(s->child[0], key);
        } else if (key == s->key) {
            return size(s->child[0]);
        } else {
            int tmp = find(s->child[1], key);
            
            if (tmp >= 0) tmp += size(s->child[0]) + 1;
            
            return tmp;
        }
    }
    
    int count(_myset *s, T key)
    {
        if (s == NULL) return 0;
        
        if (key < s->key) {
            return count(s->child[0], key);
        } else if (key == s->key) {
            return 1;
        } else {
            return count(s->child[1], key);
        }
    }
    
    void clear(_myset *s)
    {
        if (s == NULL) return;
        
        if (s->child[0] != NULL) clear(s->child[0]);
        if (s->child[1] != NULL) clear(s->child[1]);
        
        delete s;
    }
    
    T rank(_myset *s, int n)
    {
        int m = size(s->child[0]);
        
        if (n < m) {
            return rank(s->child[0], n);
        } else if (n == m) {
            return s->key;
        } else {
            return rank(s->child[1], n - m - 1);
        }
    }
    
    int lower_bound(_myset *s, T key)
    {
        if (s == NULL) return -1;
        
        if (key < s->key) {
            int tmp = lower_bound(s->child[0], key);
            
            if (tmp == -1) {
                return size(s->child[0]);
            } else {
                return tmp;
            }
        } else if (key == s->key) {
            return size(s->child[0]);
        } else {
            int tmp = lower_bound(s->child[1], key);
            
            if (tmp == -1) {
                return tmp;
            } else {
                return size(s->child[0]) + tmp + 1;
            }
        }
    }
    
    int upper_bound(_myset *s, T key)
    {
        if (s == NULL) return -1;
        
        if (key < s->key) {
            int tmp = upper_bound(s->child[0], key);
            
            if (tmp == -1) {
                return size(s->child[0]);
            } else {
                return tmp;
            }
        } else {
            int tmp = upper_bound(s->child[1], key);
            
            if (tmp == -1) {
                return tmp;
            } else {
                return size(s->child[0]) + tmp + 1;
            }
        }
    }
};

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

pair <double, double> p[200000];
myset <pair<double, double> > s;

int main()
{
    int n, i, j;
    double r;
    
    scanf("%d %lf", &n, &r);
    
    for (i = 0; i < n; i++) scanf("%lf %lf", &p[i].first, &p[i].second);
    
    sort(p, p + n);
    
    for (i = 0; i < n; i++) {
        int a;
        
        a = s.lower_bound(make_pair(p[i].first - r - 0.1, p[i].second));
        
        for (j = a; j < s.size(); j++) {
            pair <double, double> p1 = s.rank(j);
            
            if (dist(p1.first, p1.second, p[i].first, p[i].second) <= r * 2) break;
        }
        
        if (j == s.size()) s.insert(make_pair(p[i].first, p[i].second));
    }
    
    printf("%d\n", s.size());
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:328:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:330:72: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result