C++11: `error: expected primary-expression before ‘)’ token in code` for line sweep to find closest pair

Question

This is an attempted O(NlogN) solution to the closest pair problem, written in C++11. I used std::complex for geometry. The comparators may be confusing, to the explain: cmp initially sorts the points by x and then y, and compare_y sorts the points in the bounding box by y value.

The following are the errors I get, followed by my code.

cp.cpp: In function ‘int main()’:
cp.cpp:49:95: error: expected primary-expression before ‘)’ token
                 for (set<point>::iterator it = s.lower_bound(s.begin(), s.end(), t1, compare_y); it < s.upper_bound(s.begin(), s.end(), t2, compare_y); ++it) {
                                                                                               ^
cp.cpp:49:150: error: expected primary-expression before ‘)’ token
                 for (set<point>::iterator it = s.lower_bound(s.begin(), s.end(), t1, compare_y); it < s.upper_bound(s.begin(), s.end(), t2, compare_y); ++it) {

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;

// define x, y as real(), imag()
typedef complex<double> point;
#define x real()
#define y imag()

bool cmp(point a, point b) {
    if (a.x < b.x) return true;
    if (a.x - b.x < EPS && a.y < b.y) return true;
    return false;
}

struct compare_y {
    bool operator() (const point& lhs, const point& rhs) const{
        if (lhs.y < rhs.y) return true;
    }
};

int main() {
    int n;
    while (scanf("%d", &n) && n != 0) {

        vector<point> coord;
        for (int i=0; i<n; ++i) {
            double xi, yi;
            scanf("%lf%lf", &xi, &yi);
            point t(xi, yi);
            coord.push_back(t);
        }
        sort(coord.begin(), coord.end(), cmp);

        double h = 10000000;
        set<point, compare_y> s;
        s.insert(coord[0]);
        for (int i=1; i<n; ++i) {

            for (auto pt:s) {
                if (abs(pt-coord[i])+EPS > h) { // bound by x
                    s.erase(pt);
                }
            }
            point t1 = coord[i]; t1.imag(t1.y - h);
            point t2 = coord[i]; t2.imag(t2.y + h);
            for (set<point>::iterator it = s.lower_bound(s.begin(), s.end(), t1, compare_y); it < s.upper_bound(s.begin(), s.end(), t2, compare_y); ++it) {
                h = min(h, abs(*it-coord[i]));
            }


            s.insert(coord[i]);
        }
        if (h + EPS >= 10000)
            printf("INFINITY\n");
        else
            printf("%.4lf\n", h);

    }
}

Why was there a downvote? Is my question inappropriate for this site? — Jack Pan, Jul 19 '16 at 14:59
The error is because you are trying to pass `compare_y` where a function argument is expected, but `compare_y` is the name of a type, not an object. There are other problems that you'll need to fix too though, as Barry explains. — Jonathan Wakely, Jul 19 '16 at 15:05

score 3 · Accepted Answer · edited May 23 '17 at 11:44

First of all, don't use <bits/stdc++.h>.

Second of all, you are confusing the member function std::set::lower_bound() with the algorithm std::lower_bound() - they take different arguments. The member function just takes a single argument (the other three are implied - the range of the set and the comparator. Though even for std::lower_bound(), you're providing the comparator incorrectly as that argument needs to be an object and you're simply providing a typename).

Thirdly, s is a std::set<point, compare_y> so those member functions return a std::set<point, compare_y>::iterator and not a std::set<point>::iterator.

Fourthly, std::set<point, compare_y>::iterator is not random-access and thus does not have operator< defined. You need to use !=.

The correct line would be:

for (std::set<point, compare_y>::iterator it = s.lower_bound(t1); it != s.upper_bound(t2); ++it) {

or just :

for (auto it = s.lower_bound(t1); it != s.upper_bound(t2); ++it) {

Your answer works perfectly, I'll accept when I'm allowed to in 5 minutes. Thanks. — Jack Pan, Jul 19 '16 at 15:04
I realize this is out of the bounds of the question, but if you could give one more tip: I got a time limit exceeded for this code (and I didn't when I just brute forced with line sweep (no set)). Do you see anything that would make this code not run in time? I'm not going to make you answer this for the correct answer; I'll accept it anyway. Just wondering if you could give a bonus. — Jack Pan, Jul 19 '16 at 15:08

C++11: `error: expected primary-expression before ‘)’ token in code` for line sweep to find closest pair

1 Answers1