Cod sursa(job #2204840)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 17 mai 2018 01:41:11
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 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;
}

std::vector <int> G[1 + MAXM];

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);
        G[v[i].x].push_back(i);
    }
    int ans = 0;
    for(int i = 1; i <= m; i++){
        fscanf(fi,"%d%d", &w[i].x, &w[i].y);
        for(auto y: G[w[i].x])
            if(!okk[i] && v[y].y == w[i].y) okk[i] = 1, ans++;
    }

    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);

    int tmp = 0;
    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){
            Active.push_back(y);
        }
        else if(y.tp == POINT_TYPE){
            if(okk[y.A]) continue;
            if(!Active.size()) continue;

            int con = 0, ok = 1;
            for(int i = 0; i < Active.size() && ok; i++)
                if(onSegm(i, y.A)) ans++, ok = 0;
                else if(left(i, y.A)) con++;
            if(ok && con % 2 == 1){
                okk[y.A] = 1;
                ans++;
            }
        }
    }
    fprintf(fo,"%d\n", ans);

    return 0;
}