Point in Polygon

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <complex.h>
#include <limits.h>

typedef struct {
    int64_t x;
    int64_t y;
} coord;
#define cross(a,b) ( (a).x*(b).y-(b).x*(a).y )
#define minus(a,b) ((coord) {(a).x-(b).x, (a).y-(b).y})
#define plus(a,b) ((coord) {(a).x+(b).x, (a).y+(b).y})
#define dot(a,b) ((a).x*(b).x + (a).y*(b).y)
#define ceq(a,b) ((a).x == (b).x && (a).y == (b).y)

#define min(a,b) ((a)<(b)? (a) : (b))
#define max(a,b) ((a)>(b)? (a) : (b))

#define LOOP(i,s,e) for (uint64_t i = (s); i < (e); i++)
#define SCAN(...) if (scanf(__VA_ARGS__) == 0) return EXIT_FAILURE

coord *poly;
uint64_t edges;

bool intersect(coord a, coord b, coord c, coord d){
    if (ceq(a,c) || ceq(a,d) || ceq(b,c) || ceq(b,d))
        return true;
    coord ab = minus(b,a);
    coord ac = minus(c,a);
    coord ad = minus(d,a);
    coord cd = minus(d,c);
    if (cross(ab, cd) == 0 && cross(ab, ac) == 0){
        // printf("same line !\n");
        int64_t abc = dot(ab, ac);
        int64_t abd = dot(ab, ad);
        int64_t abb = dot(ab, ab);
        return (0 <= abc && abc <= abb) || (0 <= abd && abd <= abb) || (min(abc, abd) <= 0 && abb <= max(abc, abd));
    }
    coord ca = minus(a, c);
    coord cb = minus(b, c);
    int64_t abc = cross(ab, ac);
    int64_t abd = cross(ab, ad);
    int64_t cda = cross(cd, ca);
    int64_t cdb = cross(cd, cb);
    // printf("abc:%d, abd:%d, cda:%d, cdb:%d\n", abc, abd, cda, cdb);
    return
        (abc == 0 || abd == 0 || ((abc ^ abd) & LONG_MIN) == LONG_MIN) &
        (cda == 0 || cdb == 0 || ((cda ^ cdb) & LONG_MIN) == LONG_MIN);
}

bool boundary(coord a){
    LOOP(i, 0, edges){
        coord ba = minus(a, poly[i]);
        coord bc = minus(poly[i+1], poly[i]);
        if (cross(ba,bc) == 0){
            int64_t bac = dot(ba, bc);
            int64_t bcc = dot(bc, bc);
            if (bac >= 0 && bac <= bcc){
                return true;
            }
        }
    }
    return false;
}

bool inside(coord p){
    int64_t acc = 0;
    coord far_point = {4294967295, p.y+1};
    LOOP(i, 0, edges){
        if (intersect(p, far_point, poly[i], poly[i+1])){
            acc++;
        }
    }
    return (acc%2==1);
}

int main() {
    uint64_t m;
    SCAN("%ld %ld", &edges, &m);

    poly = (coord*) malloc((edges+1) * sizeof(coord));
    LOOP(i, 0, edges)
        SCAN("%ld %ld", &poly[i].x, &poly[i].y);
    poly[edges] = poly[0];

    coord p;
    LOOP(i, 0, m){
        SCAN("%ld %ld", &p.x, &p.y);
        if (boundary(p)){
            printf("BOUNDARY\n");
        } else if (inside(p)){
            printf("INSIDE\n");
        } else {
            printf("OUTSIDE\n");
        }
    }



    return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: UNKNOWN