Cod sursa(job #2204725)

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

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

#define EDGE_TYPE_ST 1
#define POINT_TYPE 2
#define 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 int S(Point A, Point B, Point C){
    return (A.x * B.y + A.y * C.x + B.x * C.y) -
           (A.x * C.y + A.y * B.x + C.x * B.y);
}
inline int left(int ind, int pt){
    return S(v[Active[ind].A], w[pt], v[Active[ind].B]) <= 0;
}
inline int onSegm(int ind, int pt){
    Point A = v[Active[ind].A];
    Point B = v[Active[ind].B];
    Point M = w[pt];

    return S(A, B, M) == 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, var = std::min(v[y.A].x, v[y.B].x);
            while(i < Active.size() && std::max(v[Active[i].A].x, v[Active[i].B].x) <= var) 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++;
        }
        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(auto y: V){
        if(y.tp == EDGE_TYPE_ST){
            int i = 0, var = std::min(v[y.A].x, v[y.B].x);
            while(i < Active.size() && std::max(v[Active[i].A].x, v[Active[i].B].x) <= var) 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){
            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 += (ok + 1) % 2;
        }
    }
    fprintf(fo,"%d", ans);

    return 0;
}