CONTAIN - Why did this failed on subtask 1?

solution : CodeChef: Practical coding for everyone

Why this line?

if (polygon.size() < 4) break;

Removing it gives RTE !?

when polygon is empty,

the line next to it is using polygon and expecting polygon to be non - empty … thus this is a check for that condition.

i am generating polygons such that it will have minimum 4 points to return
like for a simple triangle (1,1),(1,2),(2,2)
my code’s polygon would be (1,1),(1,2),(2,2),(1,1).
thus an empty polgon must have size < 4.

Why did you wrote your Convex Hull algo in that way? It is confusing. If the CH of points is triangle why is returning 4 points?

because i am storing first point twice in my polygon, so that, while checking for point inside polygon, my code will test point for every line segment of polygon, i thought it would be little easy…

convex hull algo has two parts, first giving upper cover of the polygon and then lower cover.

Sorry, I’m not good with geo. When I did this Q, I copy pasted everything from internet ( :sweat_smile: :stuck_out_tongue:). If you’re sure about your CV and removing points function then issue may be with point in polygon (not sure though). You may try to generate some random cases and compare answers with an AC code.

No problem mate, thankyou for trying …

i also copypasted a funtion for point in polygon thing when the contest was running.

and i think i am done with current contest :rofl:. so was just passing time with the problem.

1 Like

Good… Maybe I should also learn geo (I’m too lazy :stuck_out_tongue_winking_eye:).

1 Like

i found a mistake it was technical one,

in the section of point in polygon … i was compaing an int and double values.
they were causing the problem… AC.

this is the first time i encountered this error.

1 Like

I have still one doubt polygon is actually convex hull of some points, so minimum size of it is 3 and since you’re including 1 more vertex then min size would be 4. But why that condition? Shouldn’t that condition be always false and polygon.size() will always be greater than or equal to 4. Removing it gives RE meaning that condition actually becomes true…but why??

yes when that condion is true that means no more polygons can be extracted so we need to break out of loop.

conditions become true when convex hull is called with collinear points… and when then happens convex hull will not return any polygon. because polygon’s size would be zero.

and if the same empty container (polygon) is passed to remain() , (wich actually deletes polygon’s points from our Points container), which first of all sorts the copy of polygon points (which was passed to through arguments) may be that is where RE is coming from as we are trying to sort an empty container.

1 Like

Thanks! Got it!

1 Like

sort() is not the colpurit…

this code of remain…

int i = 0 , j = 1;
	vector<pair<int,int>> ret;
	sort(p.begin(),p.end());
	for (; i < P.size() ; i ++) {
		if (P[i] == p[j]) { 
			j++; 
			continue;
		}
		ret.push_back(P[i]);
	}

if you see here i am not caring if p is empty or not … i am simply calling p[j], and j >= 1;
this exactly where RE came from … :sweat_smile:

1 Like

Ya! understood! Thanks! :blush:

1 Like