CONTAIN - Editorial

editorial
, , , , ,
43

I CANNOT FIND MY MISTAKE
PASSING FOR TC + EXAMPLES GIVEN ABOVE
MY CODE IS VERY SMALL
I WOULD BE GLAD IF SOMEONE COULD GIVE A TC/HELP ME DEBUG
I ALWAYS GET STUCK ON CONVEX HULL QUESTIONS :frowning:
https://www.codechef.com/viewsolution/34491671

44

When it comes to algorithms concerned with geometry, you should try to avoid floating-point computations as much as you can. We needed to check if a point lies strictly inside a given polygon or not, and we can use just cross products to do that. I’ll explain with the code, for lack of good animation or art skills (or probably because I’m a little bored):

bool inside(const polygon& layer, const point& p) {
    int n = layer.size();
    int direction = orientation(layer[n - 1], p, layer[0]);
    if(!direction) return false;
    for(int i = 0; i < n - 1; ++i) {
        int sense = orientation(layer[i], p, layer[i + 1]);
        if(sense == (-direction) || !sense) return false;
    }
    return true;
}

The procedure takes two geometric objects: the polygon (one of the convex layers) and a point. It will return true if the layer strictly contains the point, and false otherwise. First we compute the orientation of the point with respect to any segment of the polygon (direction). Without the loss of generality, I chose the one connecting the last and first vertex. The idea is this: the point is inside the polygon if it is oriented either clockwise (orientation = -1) or anticlockwise (orientation = 1) with respect to every segment of the polygon (sense of the segment). You can visualize it as follows: imagine a weird shaped clock with two hands as usual, with tails at the point and heads sweeping the polygon vertices as we go from one segment to the next. The point is inside if the hands do not change relative order. The way you tackle the points on the boundary is by taking care of collinearity (orientation = 0). If the three points (vertex - point - vertex) are collinear, it means that the point is on the line passing through the segment, implying that it could either be out of the polygon or on the polygon but not inside :slightly_smiling_face:

Full Solution [If Required]

1 Like
45

thanks a lot!!!

46

How to test your solution in Competitive Programming, on Linux? - YouTube watch this video if you want to learn to debug
pick any one ac code and stress test as he explains
i used this tester to debug
https://www.codechef.com/viewsolution/34495789=>my AC code

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

int random(int a, int b)
{
    return a + rand() % (b - a + 1);
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    srand(atoi(argv[1]));

    int testcases = 1;
    printf("%d\n", testcases);

    for (int tt = 1; tt <= testcases; tt++)
    {
        int n = random(2, 10);
        printf("%d ", n);
        int q = random(2, 10);
        printf("%d\n", q);
        set<pair<int, int>>s;
        while (s.size() < n)
        {
            int a = random(0, 10);
            int b = random(0, 10);
            if (!s.count({a, b}))
            {
                printf("%d %d\n", a, b);
                s.insert({a, b});
            }
        }
        for (int i = 0; i < q; ++i)
        {
            int a = random(0, 10);
            int b = random(0, 10);
            printf("%d %d\n", a, b);
        }
    }


    return 0;
}
47

I think the editorial is a bit incomplete. It took me 2 days after the contest to really get all AC’s . Few points I want to explain if someone is still not getting all AC’s.

  1. If you are using the gift wrapping algorithm and Some cases are going TLE.
    Check your algorithm for collinear points on y-axis. Solution for that is sorting points with y-coordinate before starting Jarvis march gift wrapping.
  2. If Some cases are getting WA. So the problem may be with collinear points because when we perform point to search in a polygon. We require all points to be correctly aligned as It will work on the side. So, the solution to this can be saving only endpoints of those collinear points. This will remove issues with the correct alignment of those collinear points.
  3. A simpler way to the checkpoint is in a polygon or not in O(N) is cosign of vectors one as a side and another as point and side start point(But It will work only in case of strictly inside the polygon.)
    My code is kept here
1 Like
49

Your code is between is too long. You can shorten it with

def isBetween(a, b, c):
    crossproduct = (c[1] - a[1]) * (b[0] - a[0]) - (c[0] - a[0]) * (b[1] - a[1])
    if abs(crossproduct) > 2.220446049250313e-16:
        return False
    dotproduct = (a[0] - c[0]) * (b[0] - c[0]) + (a[1] - c[1])*(b[1] - c[1])
    return dotproduct <= 0
50

https://www.codechef.com/viewsolution/34685048

Plz see my code and tell why I am getting RE (SIGSEGV) error?

51

HULL(vector v):vertices(v)
please can someone explain this

52

you should read about classes and structures in c++. That’s an assignment instruction in the constructor of the structure

53

See in my solution i am getting WA in only one test case and my whole code is alike tester’s code but for grahams scan i am sorting based on polar angle’s in CCW . But still i am getting WA in one test case my other function are absolutely correct because when i put the testers code “convex_hull” function it’s AC but with mine it’s giving WA i have checked all the possible edge cases please help @pandey_ji1 @carre.
Just see the convex hull function because this is the reason for my WA in one test case or provide me a test case which is failing

Link to my solution —> CodeChef: Practical coding for everyone

54

have you tried writing a generator of cases and comparing the output of your solution with the testster solution? That’s exactly what I would do

1 Like