OJ Board

Posted: **Fri Sep 01, 2006 11:32 pm**

My following code is getting compile error. Can anyone help me in this reagard?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define SIZE 100000

struct point{
	int x,y;
	point(){}
	point(int _x,int _y):x(_x),y(_y){}
	point operator-(point &p){point tmp(x-p.x,y-p.y);return tmp;}
	friend int operator^(point p1,point p2){return p1.x*p2.y-p1.y*p2.x;}
	bool operator<(point &p){return y<p.y || (y==p.y && x<p.x);}
};
vector<point> list;
point ref;

inline int cross_product(point &p0,point &p1,point &p2){
	return (p1-p0)^(p2-p0);
}

inline int sq_distance(point &p1,point &p2){
	return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
}

bool eqal(point &a,point &b){
	return cross_product(ref,a,b)==0;
}

bool comp(point &a,point &b){
	int cp=cross_product(ref,a,b);
	return cp<0 || (cp==0 && sq_distance(ref,a)>sq_distance(ref,b));
}

int convex_hull(vector<point> &points,int n){
	int i,top=0;
	static int stack[SIZE];
	for(i=1;i<n;i++)
		if(points[i]<points[top])
			top=i;
	swap(points[top],points[0]);
	ref=points[0];
	sort(points.begin(),points.end(),comp);
	points.erase(unique(points.begin()+1,points.end(),eqal),points.end());
	n=points.size();
	for(i=0;i<3;i++)	stack[i]=i;
	for(i=top=3;i<n;i++){
		while(cross_product(points[i],points[stack[top-1]],points[stack[top-2]])>0)
			top--;
		stack[top++]=i;
	}
	for(i=1;i<top;i++)
		points[i]=points[stack[i]];
	return top;
}

void main(){
	int p,i;
	while(scanf("%d",&p)==1){
		list.resize(p);
		for(i=0;i<p;i++)	scanf("%d%d",&list[i].x,&list[i].y);
		p=convex_hull(list,p);
		printf("%d\n",p);
	}
}

Here are the compile errors

Code: Select all

/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h: 
In function `const struct point & __median<point, bool (*)(point &, 
point &)>(const point &, const point &, const point &, bool (*)(point &, 
point &))':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:1304:   
instantiated from `__introsort_loop<point *, point, int, bool (*)(point 
&, point &)>(point *, point *, point *, int, bool (*)(point &, point &))'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:1332:   
instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:64: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:64: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:65: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:65: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:67: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:67: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:71: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:71: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:73: 
conversion from `const point' to `point &' discards qualifiers
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_algo.h:73: 
conversion from `const point' to `point &' discards qualifiers

Posted: **Sat Sep 02, 2006 1:30 am**

The compiler is telling you everything, just read the error message and fix the code.

Hint: why are you using references when you should be using const-references? In particular using references in comp breaks the interface of comparators.

Posted: **Sat Sep 02, 2006 7:27 am**

Thanks.

Changing

Code: Select all

bool comp(point &a,point &b)
bool eqal(point &a,point &b)
inline int sq_distance(point &p1,point &p2)
inline int cross_product(point &p0,point &p1,point &p2)

to

Code: Select all

bool comp(const point &a,const point &b)
bool eqal(const point &a,const point &b)
inline int sq_distance(point p1,point p2)
inline int cross_product(point &p0,point p1,point p2)

resolved the problem. I'd come with such because I'm trying to use a global variable in the comparators.

Posted: **Sat Sep 02, 2006 7:51 am**

The use of reference in cross product is still incorrect - you're not changing p0 inside cross_product, are you? Also in most cases functions like sq_distance and cross_product should pass their arguments by const references instead of values (the only exceptions are primitive types and very small classes that are cheaper to copy than to reference).

Posted: **Sat Sep 02, 2006 8:13 am**

Thank you Krzysztof Duleba. I've rewritten sq_distance() as

Code: Select all

inline int sq_distance(const point &p1,const point &p2)

But if I try to pass the arguments by const references to cross_product() as well then I come with new compile errors which seems to be related to the operator-().

Posted: **Sat Sep 02, 2006 8:50 am**

Oh, that's right. operator- should use const references, other operators too. And most of the time they should be const as well, to promise not to modify the objects they are operating on (as in bool operator-(const point &p)const{...} - note the second const that applies to the implied argument).

BTW: main should return int, not void.

Another hint: turn on the highest level of warnings in your compiler (I usually use -Wall -W -Wshadow and even -Werror). You will avoid many silly mistakes this way (I know I have).

Posted: **Sat Sep 02, 2006 9:02 am**

Thank you so much Krzysztof Duleba. You're damn expert in C++.

OJ Board

Compile error with comparer function

Compile error with comparer function