Cod sursa(job #2204744)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 16 mai 2018 22:51:14
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.67 kb
#include <bits/stdc++.h>
#define MAXN 800
#define MAXM 60000

struct Point{ int x, y;} v[1 + MAXN], w[1 + MAXM];
int okk[1 + MAXM];

int EDGE_TYPE_ST = 1;
int POINT_TYPE = 2;
int EDGE_TYPE_FN = 3;
struct Event{ int tp, A, B;} NIL;
std::vector <Event> V;
bool cmp(Event A, Event B){
    int rA, rB;
    if(A.tp == EDGE_TYPE_FN) rA = v[A.B].y;
    else if(A.tp == EDGE_TYPE_ST) rA = v[A.A].y;
    else rA = w[A.A].y;

    if(B.tp == EDGE_TYPE_FN) rB = v[B.B].y;
    else if(B.tp == EDGE_TYPE_ST) rB = v[B.A].y;
    else rB = w[B.A].y;

    if(rA != rB) return rA > rB;
    return A.tp < B.tp;
}
std::vector <Event> Active;

inline long long S(Point A, Point B, Point C){
    return (1LL * A.x * B.y + 1LL * A.y * C.x + 1LL * B.x * C.y) -
           (1LL * A.x * C.y + 1LL * A.y * B.x + 1LL * C.x * B.y);
}
inline int left(int ind, int pt){
    return S(v[Active[ind].A], w[pt], v[Active[ind].B]) <= 0LL;
}
inline int onSegm(int ind, int pt){
    Point A = v[Active[ind].A];
    Point B = v[Active[ind].B];
    Point M = w[pt];

    if(M.y < std::min(A.y, B.y) || M.y > std::max(A.y, B.y)) return 0;
    return S(A, B, M) == 0LL;
}
inline int check(Event A, Event B){
    return S(v[A.A], v[B.B], v[A.B]) <= 0;
}

int main(){
    FILE*fi,*fo;
    fi = fopen("poligon.in","r");
    fo = fopen("poligon.out","w");

    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        fscanf(fi,"%d%d", &v[i].x, &v[i].y);
    for(int i = 1; i <= m; i++)
        fscanf(fi,"%d%d", &w[i].x, &w[i].y);

    for(int i = 1; i <= n; i++){
        int a = i, b = i % n + 1;
        if(v[a].y < v[b].y) std::swap(a, b);
        V.push_back({EDGE_TYPE_ST, a, b});
        V.push_back({EDGE_TYPE_FN, a, b});
    }
    for(int i = 1; i <= m; i++)
        V.push_back({POINT_TYPE, i, i});
    std::sort(V.begin(), V.end(), cmp);

    int ans = 0;
    for(auto y: V){
        if(y.tp == EDGE_TYPE_ST){
            int i = 0;
            while(i < Active.size() && check(Active[i], y)) i++;
            Active.push_back(NIL);
            for(int j = Active.size() - 1; j > i; j--)
                Active[j] = Active[j - 1];
            Active[i] = y;
        }
        else if(y.tp == POINT_TYPE){
            /*printf("%d %d\n", w[y.A].x, w[y.A].y);
            for(auto y: Active)
                printf("%d %d      %d %d\n", v[y.A].x, v[y.A].y, v[y.B].x, v[y.B].y);
            printf("\n");*/

            if(!Active.size()) continue;
            if(!left(0, y.A)) continue;

            int st = 0, dr = Active.size() - 1;
            while(dr - st > 1){
                int m = (st + dr) / 2;
                if(left(m, y.A)) st = m;
                else dr = m - 1;
            }
            int ok;
            if(left(dr, y.A)) ok = dr;
            else ok = st;

            if(onSegm(ok, y.A)){ ans++, okk[y.A] = 1;}
        }
        else if(y.tp == EDGE_TYPE_FN){
            int i = 0;
            while(Active[i].A != y.A || Active[i].B != y.B) i++;
            for(int j = i; j + 1 < Active.size(); j++)
                Active[j] = Active[j + 1];
            Active.pop_back();
        }
    }

    Active.clear();
    for(int i = 0; i < V.size(); i++)
        if(V[i].tp == 3) V[i].tp = 2;
        else if(V[i].tp == 2) V[i].tp = 3;
    POINT_TYPE = 3;
    EDGE_TYPE_FN = 2;
    std::sort(V.begin(), V.end(), cmp);
    for(auto y: V){
        if(y.tp == EDGE_TYPE_ST){
            int i = 0;
            while(i < Active.size() && check(Active[i], y)) i++;
            Active.push_back(NIL);
            for(int j = Active.size() - 1; j > i; j--)
                Active[j] = Active[j - 1];
            Active[i] = y;
        }
        else if(y.tp == EDGE_TYPE_FN){
            int i = 0;
            while(Active[i].A != y.A || Active[i].B != y.B) i++;
            for(int j = i; j + 1 < Active.size(); j++)
                Active[j] = Active[j + 1];
            Active.pop_back();
        }
        else if(y.tp == POINT_TYPE){
            //printf("%d %d\n", w[y.A].x, w[y.A].y);
            //for(auto y: Active)
            //    printf("%d %d      %d %d\n", v[y.A].x, v[y.A].y, v[y.B].x, v[y.B].y);
            //printf("\n");
            if(!Active.size()) continue;
            if(!left(0, y.A)) continue;

            int st = 0, dr = Active.size() - 1;
            while(dr - st > 1){
                int m = (st + dr) / 2;
                if(left(m, y.A)) st = m;
                else dr = m - 1;
            }
            int ok;
            if(left(dr, y.A)) ok = dr;
            else ok = st;

            if(!okk[y.A]) ans += (ok + 1) % 2;
        }
    }
    fprintf(fo,"%d\n", ans);

    return 0;
}