Description

Recently, scientists finally find a way to produce unlimited energy. The scientists call it "Cat-Toast".

In case that someone might not know:
While buttered toast falls onto the ground, it will always land with its buttered side - Falling Toast Theorem(FTT)
While cats fall onto the ground, they will always land with their four feets. - Falling Cat Theorem(FCT)
By FTT, we can assume that if we put butter on both sides of the toast, we might create a perpetual motion machine, because by FTT, we know that the buttered side will land onto the ground. However, there are two buttered sides. If any side of the toast lands, there will be a contradiction, so the toast will never fall and continue spinning around. We can apply the same way on FCT.
However, there is a big problem. if we just put two buttered toasts or two cats together, there will be no momentum, and obviously it won't spin except for any external force, which cannot be a perpetual motion machine. This problem had confused scientists for centuries.
Recently, scientists finally got a breakthrough progress. They combined a cat and a buttered toast and it just spins by itself! Due to the difference mass of a cat and a buttered toast, the machine itself will provide the momentum to spin, and it will never fall onto the ground (due to the contradiction we proved before), the first perpetual motion machine was born!

The original video is here.

Scientists found that if two cat-toasts' distance are equal to or closer than r, there will be a collision which cause a small black hole and soon disappear, which is very dangerous. The cat-toast must be secured separately. Also, if there are multiple cat-toasts that will collide, those cat-toasts will all collide together and spawn exactly one black hole. If there's any problem, you may refer to Sample I/O.
One day in NTHU, a servitor just carries a lot of cat-toasts, each with a secured box. He accidently falls down and all the cat-toasts just drop out of their own boxes.
Now given r and all the coordinates of all cat-toasts, the servitor wants to know how many cat-toasts remains there after some destructive collisions and how many black holes spawned. 

Note that the distance of two cat-toasts is sqrt( (x1-x2)^2 + (y1-y2)^2 ), where (x1,y1) and (x2,y2) are the coordinates of this two.

Input

The first line contains two integers n, r, indicate the number of cat-toast, the distance r decribed above.
The next n lines, each line contains two integers x_i, y_i, indicates the location of the i-th cat-toast.
1 <= n <= 1000, 1 <= r <= 10⁴
1 <= x_i, y_i <= 10⁴

Output

The first line of the output is the total number of cat-toasts that still remains and the total number of black holes after collisions, separated by a space.
Remember to output a '\n' at the end of the output.
(In fact, except for the problem DO ask you not to output a '\n' at the end of the output, mostly you shoul output a '\n' at the end.)

Take Sample I/O as an example, obviously cat-toast located at (5,15) and (1,15) will collide. (1,7), (1,3), and (5,3) will collide together because (1,7), (1,3) collides, and (1,3), (5,3) collides, just like a chain, or a tree.

There's only one remaining cat-toast located at (500,500) and spawned 2 black holes, so the answer is "1 2" without quotes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I have broken many girls' hearts into pieces. But none of them mad at me. None.

~ by anonymous surgeon

You're a surgeon, you need to mend those girls' hearts. Therefore you need a data structure to support some functions.

This question is about maintain a set that contains only integers.

There will be n instructions.

Each instruction will be either:

insert:

Insert a new element ai into the set. Note that if the element has already in the set, do nothing.

print:

print all the element in the set in increasing order.

min:

print the number in the set that is the smallest. If there's no number, do nothing.

range_erase:

You will have two integer l, r.

You need to erase all the elements ai in the set that l <= ai <= r

Hint: You can solve this question very fast by using std::set .

These are some functions you may use in your code:

set.begin(), set.size(), set.erase(), set.lower_bound(), set.upper_bound(), set.insert(). To traverse through your set, you may also need iterator or type auto(only in c++11!)

You can also solve this question in C.

Input

the input will contain several lines.

The first line only contains an integer n (1 <= n <= 5000)

The following are n lines.

Each lines contains a instruction list above.

Note that ai (0 <= ai <= 10^9)

Output

For each print instruction, print all the number in the set in increasing order.

Each number is separated by a single blank.(No blank at the the end!)

Remember to print \n at the end of output

For each min instruction, print the smallest number in the set.

Remember to print \n at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I/O optimization

If you encounter a TLE, you may try to use this optimization for C++ I/O functions:

std::ios_base::sync_with_stdio(false);
cin.tie(0);

And replace all std::endl with '\n'.

Do note that you must not use any of C I/O functions such as scanf, printf, fgets if you use this optimization.

<vector>

#include <iostream>
#include <vector>
#include <algorithm> // sort
int main () {
    std::vector<int> V;
    int x;
    while (std::cin >> x) {
        V.push_back(x);
    }
    for (auto t : V) std::cout << " " << t;
    std::cout << "\n";
    std::sort(V.begin(), V.end());
    for (auto t : V) std::cout<<" "<< t;
    std::cout << "\n";
}

<queue>

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int main() {
    string s;
    queue<string> q;
    while (cin >> s) {
        if (s == "Push") {
            cin >> s;
            q.push(s);
        }
        else if (s == "Pop") {
            if (q.size()>0)
                q.pop();
        }
        else if (s == "Front") {
            if (q.size() == 0)
                cout << "empty\n";
            else
                cout << q.front() << "\n";
        }
    }
}

<stringstream>

#include <string>
#include <iostream>
#include <sstream> // std::stringstream
int main () {

     std::stringstream ss;
     ss << "Hello " << 123;
     std::string s = ss.str();
     std::cout << s << '\n';
}

<set>

#include <iostream>
#include <set>
int main()
{
     std::set<int> S = {1, 2, 3, 4};
     auto search = S.find(2);
     if(search != S.end()) {
          std::cout << (*search) << '\n';
     }
     else {
          std::cout << "Not found\n";
     }
}

<stack>

#include <stack>
#include <iostream>
int main()
{
     std::stack<int> s;
     s.push( 3 ); s.push( 6 );
     s.push( 18 );
     std::cout<<s.size()<<" elements\n";
     std::cout<<"Top: "<< s.top()<< "\n";
     s.pop();
     std::cout<<s.size()<<" elements\n";
}

getline()

#include <string>
#include <iostream>
int main()
{
     std::string name;
     std::cout << "What is your name? ";
     std::getline(std::cin, name);
     std::cout << "Hello "<< name<< "\n";
}

<map>

#include <iostream>
#include <string>
#include <map>
#include <utility> // make_pair
int main()
{
     std::map<std::string, int> ID;
     ID.insert(std::make_pair("Tom", 123));
     std::cout << ID["Tom"] << "\n";
}

<string>

#include <iostream>
#include <string>
int main() {
    std::string str1, str2, out;
    while (std::cin >> str1 >> str2) {
        out.clear();
        for(auto t : str1) out.push_back(t);
        std::cout << out << '\n';
        out += str2;
        std::cout << out << '\n';
        out.pop_back();
        std::cout << out << '\n';
        for(size_t i = 0; i < out.size(); i++)
            std::cout << out[i];
        std::cout << '\n';
    }
}

Miscellaneous

For more standard library or C++ reference, please refer to this file and rename the downloaded file(12534.cpp) to reference.zip, then unzip it. There's a readme inside the zip.

If you have difficulty renaming file, try the following command on terminal (Windows)

move 12534.cpp reference.zip

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss