C++

Forum

 
Need help with a program about normalized vectors

Oriol Serrabassa (100)
A vector of points on the plane is normalized if all the following three conditions hold:

Property 1: The vector contains at least two different elements.
Property 2: The sum of all the x-coordinates of the points in the vector equals the sum of all the y-coordinates of the points in the vector.
Property 3 (called barycenter in program): The barycenter of the points in the vector does not belong to the vector.

Recall that the barycenter of a set of points is the point (x,y) of the plane which has the average value of the x-coordinates of the points as x-coordinate, and the average value of the y-coordinates of the points as y-coordinate.

Make a program that reads vectors of points on the plane and determines whether they are normalized or not.

The input consists in several lines with sequences. Each sequence describes a vector of points by means of a natural number n>0, which is followed by n pairs of real numbers x1, y1, …, xn, yn describing the coordinates of the n points in the vector.

Program must have and use:
1
2
3
 
struct Point {
      double x,y;
};

bool barycenter (const vector <Point> &v, Point &b)


That's not the fully program explained but I think it's enough.

My program works partially meaning that the private inputs (the ones I do not know) give a wrong output meanwhile the public inputs work. The public inputs are the following:

INPUT
3 0 0 0 0 0 0
4 1 0 1 1 1 0 1 0
3 0 1 0 -1 0 0
3 0 1 1 0 1 1
4 0 0 1 0 0 1 0 0
3 0 0 1 1 0 0

OUTPUT
barycenter: (0.00,0.00)
property 1 does not hold
barycenter: (1.00,0.25)
property 2 does not hold
barycenter: (0.00,0.00)
property 3 does not hold
barycenter: (0.67,0.67)
normalized vector
barycenter: (0.25,0.25)
normalized vector
barycenter: (0.33,0.33)
normalized vector


I am not quite sure what I have wrong about the program but I would guess that barycenter function is the one giving wrong returns in some cases.

Anyway here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <iostream>
#include <vector>
using namespace std;

struct Point {
	double x,y;
};

bool property1 (const vector <Point> &coordenades) {
	bool check_x = true;
	for (int i = 0; i < coordenades.size(); ++i) {
		for (int j = 0; j < coordenades.size(); ++j) {
			if (coordenades[i].x != coordenades[j].y) return true;
			if (check_x) {
				for (int k = 1; k < coordenades.size(); ++k) {
					if (coordenades[i].x != coordenades[k].x) return true;
				}
				check_x = false;
			}
		}
	}
	return false;
}

bool property2 (vector <Point> &coordenades) {
	double sum_x = 0, sum_y = 0;
	for (int i = 0; i < coordenades.size(); ++i) {
		sum_x += coordenades[i].x;
		sum_y += coordenades[i].y;
	}
	Point p;
	p.x = sum_x/coordenades.size();
	p.y = sum_y/coordenades.size();
	coordenades.push_back(p);
	if (sum_x == sum_y) return true;
	else return false;
}

bool barycenter (const vector <Point> &v, Point &b) {
	for (int i = 0; i < v.size()-1; ++i) {
		if (v[i].x == b.x and v[i].y == b.y) return false;
	}
	return true;
}


int main () {
	cout.setf (ios::fixed);
	cout.precision (2);
	int size;
	while (cin >> size) {
		vector <Point> coordenades (size);
		for (int i = 0; i < size; ++i) cin >> coordenades[i].x >> coordenades[i].y;
		if (not property1 (coordenades)) {
			property2 (coordenades);
			cout << "barycenter: (" << coordenades[size].x << "," << coordenades[size].y << ")" << endl;
			cout << "property 1 does not hold" << endl;
		}
		else	if (not property2 (coordenades)) {
				cout << "barycenter: (" << coordenades[size].x << "," << coordenades[size].y << ")" << endl;
				cout << "property 2 does not hold" << endl;
			}
			else	if (not barycenter (coordenades, coordenades[size])) {
					cout << "barycenter: (" << coordenades[size].x << "," << coordenades[size].y << ")" << endl;
					cout << "property 3 does not hold" << endl;
				}
				else {
					cout << "barycenter: (" << coordenades[size].x << "," << coordenades[size].y << ")" << endl;
					cout << "normalized vector" << endl;
				}
	}
}


Made a new barycenter function but it also doesn't work:
1
2
3
4
5
6
7
8
9
10
11
 
bool barycenter (const vector <Point> &v, Point &b) {
	for (int i = 0; i < v.size()-1; ++i) {
		for (int j = 0; j < v.size()-1; ++j) {
			if (j != i and v[i].x == b.x and v[i].x == v[j].x) {
				if (v[j].y == b.y) return false;
			}
			else	if (v[j].x == b.x and v[j].y == b.y) return false;
		}
	}
	return true;
}
Last edited on
Enoizat (1342)
Hope the following code can give you some hints.
It's a different version, so, if you don't like it, just ignore it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
 
#include <algorithm>
#include <iostream>
#include <limits>
#include <tuple>
#include <vector>

struct Point {
   Point(double xArg, double yArg)
      : x{xArg}, y{yArg}
   {}
   double x, y;
};

bool property1 (const std::vector<Point>& points);
bool areEqual(const Point& point1, const Point& point2);
bool property2 (const std::vector<Point>& points);
bool barycenter (const std::vector<Point>& points);
Point calculateAverage(const std::vector<Point> &points);
std::vector<Point> buildOneVector(const std::vector<double> &vec);
std::vector<std::vector<Point>>
   buildTestVectors(std::vector<std::vector<Point>>& testvecs);
void waitForEnter();
std::vector<Point> askUserForData();
void performControls(const std::vector<Point>& points);

int main ()
{
   std::vector<std::vector<Point>> normvect;
   buildTestVectors(normvect);

   // First step: check if our vectors are normalized
   for(size_t i{0}; i<normvect.size(); i++) {
      std::cout << "\nChecking vector " << i+1 << ":\n";
      performControls(normvect.at(i));
   }
   waitForEnter();

   // Second step: ask for new vectors and check
   int useransw = 0;
   do {
      std::cout << "\nNormalized vectors checker\n==========================\n"
                << "What do you want to do?"
                << "\n0) exit?"
                << "\n1) insert data into vector?"
                << "\nyour choice: ";
      std::cin >> useransw;
      std::vector<Point> points;
      switch (useransw) {
         case 0:
            std::cout << "\nGoodby, then.\n";
            break;
         case 1:
            points = askUserForData();
            performControls(points);
            break;
         default:
            break;
      }
   } while(useransw != 0);

   return 0;
}

// Returns true if at least two elements into vector are different
bool property1 (const std::vector<Point>& points)
{
   for(size_t i{0}; i<points.size()-1; i++) {
//      std::cout << "\nComparing point[" << i << "].x (" << points.at(i).x
//                << "), point[" << i << "].y (" <<  points.at(i).y
//                << ") and point[" << i+1 << "].x (" << points.at(i+1).x
//                << "), point[" << i+1 << "].y" << points.at(i+1).y
//                << " --> They are ";
      if(!areEqual(points.at(i), points.at(i+1))) {
//         std::cout << "different.\n";
         return true;
      }/* else {
         std::cout << "equal.\n";
      }*/
   }

   return false;
}

bool areEqual(const Point& point1, const Point& point2)
{
   return std::tie(point1.x, point1.y) == std::tie(point2.x, point2.y);
}

// Returns true if the sum of all the x-coordinates is equal to the sum
// of all the y-coordinates.
bool property2 (const std::vector<Point>& points)
{
   double sum_x = 0, sum_y = 0;
   for(const auto point: points) {
      sum_x += point.x;
      sum_y += point.y;
   }

//   std::cout << "\nSum of all the x: " << sum_x
//             << "; sum of all the y: " << sum_y << '\n';

   return sum_x == sum_y;
}

// Returns true if the barycenter point does not belong to the passed vector
bool barycenter(const std::vector<Point>& points)
{
   Point baryc = calculateAverage(points);

//   std::cout << "Barycenter: baryc.x = " << baryc.x << "; baryc.y = "
//             << baryc.y << '\n';

   auto findresult = std::find_if(std::begin(points), std::end(points),
      [&baryc] (const Point& p) {
      return (baryc.x == p.x) && (baryc.y == p.y);
   });

   return findresult == std::end(points);
}

Point calculateAverage(const std::vector<Point>& points)
{
   Point average(0.0, 0.0);
   for(const auto point : points) {
      average.x += point.x;
      average.y += point.y;
   }
   average.x /= points.size();
   average.y /= points.size();

   return average;
}

std::vector<Point> buildOneVector(const std::vector<double>& vec)
{
   std::vector<Point> pointvec;
//   int j = 0;
   for(size_t i{0}; i<vec.size(); i+=2) {
      pointvec.emplace_back(vec.at(i), vec.at(i+1));
//      std::cout << "pointvec.at(" << j << ").x: " << pointvec.at(j).x
//                << "; pointvec.at(" << j << ").y: " << pointvec.at(j).y << '\n';
//      j++;
   }
   std::cout << '\n';

   return pointvec;
}

std::vector<std::vector<Point>>
buildTestVectors(std::vector<std::vector<Point>>& testvecs)
{
   // INPUT
   // 3 0 0 0 0 0 0
   // 4 1 0 1 1 1 0 1 0
   // 3 0 1 0 -1 0 0
   // 3 0 1 1 0 1 1
   // 4 0 0 1 0 0 1 0 0
   // 3 0 0 1 1 0 0

   // First vector.
   std::vector<double> coord = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0};
   testvecs.push_back(buildOneVector(coord));

   // Second vector.
   coord.empty();
   coord = {1.0, 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 0.0};
   testvecs.push_back(buildOneVector(coord));

   // Third vector.
   coord.empty();
   coord = {0.0, 1.0, 0.0, -1.0, 0.0, 0.0};
   testvecs.push_back(buildOneVector(coord));

   // Forth vector.
   coord.empty();
   coord = {0.0, 1.0, 1.0, 0.0, 1.0, 1.0};
   testvecs.push_back(buildOneVector(coord));

   // Fifth vector.
   coord.empty();
   coord = {0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0};
   testvecs.push_back(buildOneVector(coord));

   // Sixth vector.
   coord.empty();
   coord = {0.0, 0.0, 1.0, 1.0, 0.0, 0.0};
   testvecs.push_back(buildOneVector(coord));

//   waitForEnter();

   return testvecs;
}

void waitForEnter()
{
   std::cout << "\nPress ENTER to continue...\n";
   std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

std::vector<Point> askUserForData()
{
   std::cout << "Please, tell me how many points do you want to insert: ";
   int num_of_points = 0;
   std::cin >> num_of_points;
   std::cout << "\nPlease insert data as a couple of double separated "
                "by a space.";
   Point tmppoint(0.0, 0.0);
   std::vector<Point> points;
   for(int i{0}; i<num_of_points; i++) {
      std::cout << "\npoint coordinates x y: ";
      std::cin >> tmppoint.x >> tmppoint.y;
      points.push_back(tmppoint);
   }
   std::cout << "\n\nVector built.\n";

   return points;
}

void performControls(const std::vector<Point>& points)
{
   int passed_exams = 0;
   if(property1(points)) {
      std::cout << "1) there are at least two different elements: yes!\n";
      passed_exams++;
   } else {
      std::cout << "1) *** Property 1 does not apply.\n";
      return;
   }

   if(property2(points)) {
      std::cout << "2) sum of all the x is equal to sum of all the y: yes!\n";
      passed_exams++;
   } else {
      std::cout << "2) *** Property 2 does not apply.\n";
      return;
   }

   if(barycenter(points)) {
      std::cout << "3) barycenter doesn't belong to vector: yes!\n";
      passed_exams++;
   } else {
      std::cout << "3) *** Property 3 does not apply.\n";
      return;
   }

   // Pointless check, but... like placeholder for future improvements
   if(2 < passed_exams)
      std::cout << "this vector is normalized.\n";
}


If you want to see how the code works, just uncomment the 'cout' lines.
Last edited on
TheIdeasMan (6801)
@Oriol

Just wondering if you provide a link to a wiki page about the theory for normalised vectors on a plane. I haven't seen that definition before. I searched for it, but didn't find it.

Cheers :+)
lastchance (6980)
It is quite surprising that these are described as "normalised", since there is no concept of a "norm" or distance here, whereas most vectors have a perfectly good norm describing their length.

I think that you will have some difficulty comparing two doubles for equality - as soon as you do any operations on them floating-point rounding can lead to small differences removing bitwise equality. In the program below two vectors are adjudged "equal" if the absolute value of the components of their difference is less than some small tolerance EPS (here set to 1e-20). See if this works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;


const double EPS = 1.0e-20;                                // tolerance for "effectively zero"


//======================================================================

struct Point {
   double x,y;
   Point( double X = 0.0, double Y = 0.0 ) : x(X), y(Y) {} // constructor
};


istream & operator >> ( istream &strm, Point &p )          // overload >>
{
   strm >> p.x >> p.y;
   return strm;
}


ostream & operator << ( ostream &strm, Point &p )          // overload <<
{
   strm.setf(ios::fixed);
   strm.precision(3);
   strm << "(" << p.x << ", " << p.y << ")";
   return strm;
}


Point operator + ( Point a, Point b ) { return Point( a.x + b.x, a.y + b.y ); }  


Point operator - ( Point a, Point b ) { return Point( a.x - b.x, a.y - b.y ); }  


bool operator == ( Point a, Point b ) { return ( abs( a.x - b.x ) < EPS && abs( a.y - b.y ) < EPS ); }


bool operator != ( Point a, Point b ) { return !( a == b ); }


Point sumPts( vector<Point> &coordinates )                // sum of points
{
   Point sum( 0.0, 0.0 );
   for ( Point &p : coordinates ) sum = sum + p;
   return sum;
}


Point barycentre( vector<Point> &coordinates )             // geometric centre
{                                                          //    (= centre of mass if equal masses)
   Point centre = sumPts( coordinates );
   int N = coordinates.size();
   centre.x /= N;
   centre.y /= N;
   return centre;
}


//======================================================================

bool property1( vector<Point> &coordinates )
{
   for ( Point &p : coordinates ) if ( p != coordinates[0] ) return true;      // any not equal to first means at least two distinct
   return false;                                           // default if all equal to first
}

//======================================================================

bool property2( vector<Point> &coordinates )
{
   Point s = sumPts( coordinates );                        // find sum
   return ( abs( s.x - s.y ) < EPS );                      // equal if absolute difference < tolerance
}

//======================================================================

bool property3( vector<Point> &coordinates, Point &centre )
{
   centre = barycentre( coordinates );
   for ( Point &p : coordinates ) if ( centre == p ) return false;             // barycentre found in vector
   return true;                                            // default if not found
}

//======================================================================

int main()
{
   int N;

   cout << "Enter number of points, followed by requisite pairs of points: ";

   cin >> N;
   vector <Point> coordinates( N );
   for ( int i = 0; i < N; i++ ) cin >> coordinates[i];


   Point centre;
   bool prop1 = property1( coordinates );
   bool prop2 = property2( coordinates );
   bool prop3 = property3( coordinates, centre );


   cout << "\nPoints are: ";
   for ( Point &p : coordinates ) cout << p << " ";
   cout << endl;

   cout << boolalpha << "Property 1: " << prop1 << endl;
   cout << boolalpha << "Property 2: " << prop2 << endl;
   cout << boolalpha << "Property 3: " << prop3 << endl;

   cout << "\nBarycentre is " << centre << endl;

   if ( prop1 && prop2 && prop3 ) cout << "\nSet of points is normalised";
   else                           cout << "\nSet of points is not normalised";
}


Enter number of points, followed by requisite pairs of points: 
4 1 0 1 1 1 0 1 0

Points are: (1.000, 0.000) (1.000, 1.000) (1.000, 0.000) (1.000, 0.000) 
Property 1: true
Property 2: false
Property 3: true

Barycentre is (1.000, 0.250)

Set of points is not normalised


Enter number of points, followed by requisite pairs of points: 
4 0 0 1 0 0 1 0 0

Points are: (0.000, 0.000) (1.000, 0.000) (0.000, 1.000) (0.000, 0.000) 
Property 1: true
Property 2: true
Property 3: true

Barycentre is (0.250, 0.250)

Set of points is normalised

Last edited on
Enoizat (1342)
Awesome neat and effective code, @lastchance.

lastchance (6980)
Thanks @Enoizat, but it has to be tested on the OP's undisclosed input data yet ...
Oriol Serrabassa (100)
@TheIdeasMan The problem itself gives the definition of a normalized vector

@lastchance Thanks for the code but I cannot compile it since you use elements of C++11 (range-based 'for' loops are not allowed in C++98 mode). This: for ( Point &p : coordinates )
If you could fix it, it would be nice. I would do it myself if I knew how.
Last edited on
lastchance (6980)
Hi, @Oriol Serrabassa,

It has taken me a long time to get to C++11 too! You could run the code in C++ shell to test it.

Alternatively, (and sorry, I haven't checked this, so there might be errors):
for ( Point &p : coordinates ) sum = sum + p;
becomes
for ( int i = 0; i < coordinates.size(); i++ ) sum = sum + coordinates[i];

for ( Point &p : coordinates ) if ( p != coordinates[0] ) return true;
becomes
for ( int i = 0; i < coordinates.size(); i++ ) if ( coordinates[i] != coordinates[0] ) return true;

for ( Point &p : coordinates ) if ( centre == p ) return false;
becomes
for ( int i = 0; i < coordinates.size(); i++ ) if ( centre == coordinates[i] ) return false;

for ( Point &p : coordinates ) cout << p << " ";
becomes
for ( int i = 0; i < coordinates.size(); i++ ) cout << coordinates[i] << " ";
Last edited on
Oriol Serrabassa (100)
After I tweaked your code a bit @lastchance to respect the output format, I got this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;

const double EPS = 1.0e-20;

struct Point {
   double x,y;
   Point( double X = 0.0, double Y = 0.0 ) : x(X), y(Y) {} // constructor
};

istream & operator >> ( istream &strm, Point &p )
{
   strm >> p.x >> p.y;
   return strm;
}

ostream & operator << ( ostream &strm, Point &p )
{
   strm.setf(ios::fixed);
   strm.precision(2);
   strm << "(" << p.x << ", " << p.y << ")";
   return strm;
}

Point operator + ( Point a, Point b ) { return Point( a.x + b.x, a.y + b.y ); }  

Point operator - ( Point a, Point b ) { return Point( a.x - b.x, a.y - b.y ); }  

bool operator == ( Point a, Point b ) { return ( abs( a.x - b.x ) < EPS && abs( a.y - b.y ) < EPS ); }

bool operator != ( Point a, Point b ) { return !( a == b ); }

Point sumPts( vector<Point> &coordinates )
{
   Point sum( 0.0, 0.0 );
   for ( int i = 0; i < coordinates.size(); i++ ) sum = sum + coordinates[i];
   return sum;
}

Point barycentre( vector<Point> &coordinates )             
{
   Point centre = sumPts( coordinates );
   int N = coordinates.size();
   centre.x /= N;
   centre.y /= N;
   return centre;
}

bool property1( vector<Point> &coordinates )
{
   for ( int i = 0; i < coordinates.size(); i++ ) if ( coordinates[i] != coordinates[0] ) return true;
   return false;
}

bool property2( vector<Point> &coordinates )
{
   Point s = sumPts( coordinates );                        
   return ( abs( s.x - s.y ) < EPS );                      
}

bool property3( vector<Point> &coordinates, Point &centre )
{
   centre = barycentre( coordinates );
   for ( int i = 0; i < coordinates.size(); i++ ) if ( centre == coordinates[i] ) return false;
   return true;                                         
}

int main()
{
   int N;

   while (cin >> N) {
       vector <Point> coordinates( N );
       for ( int i = 0; i < N; i++ ) cin >> coordinates[i];
    
       Point centre;
       bool prop1 = property1( coordinates );
       bool prop2 = property2( coordinates );
       bool prop3 = property3( coordinates, centre );
    
       cout << "barycenter: " << centre << endl;
    
      if (not prop1) cout << "property 1 does not hold" << endl;
      else	if (not prop2) cout << "property 2 does not hold" << endl;
    	else	if (not prop3) cout << "property 3 does not hold" << endl;
    		else	if ( prop1 && prop2 && prop3 ) cout << "normalized vector" << endl;
   }
}

Sadly, this code doesn't work either, private inputs give wrong output in some case.
If private inputs, would at less give you an input example of when your code fails...
lastchance (6980)
Ah well, if you ever find out which point combinations are causing it to fail ... do let us know!

Some of these online marking systems are irritatingly pedantic about the form of output they require and mark something wrong unless it conforms to their dizzy standards.
TheIdeasMan (6801)
Oriol Serrabassa wrote:
@TheIdeasMan The problem itself gives the definition of a normalized vector


Yes, but I would like a formal definition of it, on wiki for example :+)

It is very different from my concept of a normalised vector. This seems to be for a set of vectors. Propertied 2 and 3 seem weird.

What is the practical use of this definition?
Oriol Serrabassa (100)
Think it like your boss (or whoever who has influence over you) told you to make a program where everytime you use 1 it changes to 2, so 1 + 2 = 2 + 2 = 4.

Just don't question the program functionality even if it's wrong or it doesn't do nothing useful at less in this post. Just do what the problem says and that's all.

That's scary by the way:
:+)
Last edited on
TheIdeasMan (6801)
Right, so even that the assignment may be real, the "science" is false, that's all I wanted to know.

What is scary about smiley faces? :+)
Oriol Serrabassa (100)
Then refrain from posting if you have no intention to help.

Maybe tomorrow I will have a solution for the problem, I will say something then
Oriol Serrabassa (100)
No progress at all yet.

I will look the code very carefully during this weekend (plus Monday is multinational holiday).
Last edited on
Topic archived. No new replies allowed.