Cod sursa(job #2208569)

Utilizator amaliarebAmalia Rebegea amaliareb Data 30 mai 2018 15:07:18
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 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_FN = 1;
int EDGE_TYPE_ST = 2;
int POINT_TYPE = 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, M, B) == 0LL;
}
inline int check(Event A, Event B){
    if(A.A == B.A)
        return S(v[A.A], v[B.B], v[A.B]) <= 0;
    return S(v[A.A], v[B.A], 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].y, &v[i].x);
    for(int i = 1; i <= m; i++)
        fscanf(fi,"%d%d", &w[i].y, &w[i].x);

    int ans = 0;
    for(int i = 1; i <= n; i++){
        int a = i, b = i % n + 1;
        if(v[a].y == v[b].y){
            for(int j = 1; j <= m; j++)
                if(!okk[j] && w[j].y == v[a].y && w[j].x >= std::min(v[a].x, v[b].x) && w[j].x <= std::max(v[a].x, v[b].x))
                    okk[j] = 1, ans++;
        }
        else{
            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);

    for(auto y: V){
        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 == 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){
            if(okk[y.A]) continue;
            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 ans += (ok + 1) % 2;
        }
    }
    fprintf(fo,"%d\n", ans);

    return 0;
}