Cod sursa(job #2892373)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 21 aprilie 2022 19:21:53
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#define Nmax 805
#define Mmax 60002
#define eps 0.00000001
using namespace std;
 
ifstream f("poligon.in");
ofstream g("poligon.out");
 
int n,m,nrL,x,y,nr,X;
 
struct point{
    int x,y;
}P[Nmax];
 
struct line{
    point A,B;
 
    line(point _A,point _B){
        A = _A;
        B = _B;
        if (A.x>B.x) swap(A,B);
    }
 
    line(){}
 
    bool operator == (const line &oth) const{
        return A.x==oth.A.x && A.y == oth.A.y && B.x == oth.B.x && B.y == oth.B.y;
    }
}L[Nmax];
 
struct event{
    line L;
    bool add;
};
 
vector<int> M[Mmax];
vector<event> E[Mmax];
vector<line> S;
 
void dell(line L){
    for(int i=0;i<S.size();i++)
        if (S[i]==L){
            for (;i+1<S.size();i++) S[i] = S[i+1];
            S.pop_back();
            return;
        }
}
 
static double getY(line &L, int x){
    return (double)(x - L.A.x) * (L.B.y - L.A.y) / (L.B.x - L.A.x) + L.A.y;
}
 
int UPline(int x,int y){
    int p = 1, st = 0;
    if (S.empty()) return 0;
    for (;p<S.size();p<<=1);
    for (;p>=1;p>>=1){
        if (st+p<S.size() && abs(getY(S[st+p],x) - y)<=eps) return 1;
        if (st+p<S.size() && getY(S[st+p],x) > y) st+=p;
    }
    if (abs(getY(S[st],x) - y)<=eps) return 1;
    if (getY(S[st],x) > y) st++;
    return st;
}
 
bool comp(line L1,line L2){
    if (abs(getY(L1,X) - getY(L2,X)) < eps)
        return (L1.B.y > L2.B.y || L1.A.y > L2.A.y);
    return getY(L1,X) > getY(L2,X);
}
 
int main()
{
    f>>n>>m;
    for (int i=1;i<=n;i++) f>>P[i].x>>P[i].y;
    for (int i=1;i<=m;i++) f>>x>>y,M[x].push_back(y);
    P[n+1] = P[1];
    for (int i=1;i<=n;i++)
        if (P[i].x!=P[i+1].x) L[++nrL] = *new line(P[i],P[i+1]);
        else
            for (int j=0;j<M[P[i].x].size();j++)
                if (min(P[i].y,P[i+1].y)<=M[P[i].x][j] && max(P[i].y,P[i+1].y)>=M[P[i].x][j])
                    nr++,M[P[i].x][j] = -1;
    for (int i=1;i<=nrL;i++){
        E[L[i].A.x].push_back({L[i],true});
        E[L[i].B.x].push_back({L[i],false});
    }
    for (int i=0;i<=60000;i++){
        for (int j=0;j<E[i].size();j++)
            if (E[i][j].add) S.push_back(E[i][j].L);
            else dell(E[i][j].L);
        if (!E[i].empty() || (i>0 && !E[i-1].empty())) X = i,sort(S.begin(),S.end(),comp);
        for (int j=0;j<M[i].size();j++) if (M[i][j]!=-1 && UPline(i,M[i][j])%2) nr++;
    }
 
    g<<nr;
    return 0;
}