Cod sursa(job #2191371)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 2 aprilie 2018 18:01:51
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.85 kb
#include <fstream>
#include <vector>
#include <cmath>
#define Nmax 805
#define Mmax 60002
#define eps 0.0000006
using namespace std;

ifstream f("poligon.in");
ofstream g("poligon.out");

int n,m,nrL,x,y,nr;

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;

bool comp(point A,point B) {return A.x<B.x;}

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

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 ans = 0;
    for (auto it : S) if (getY(it,x) > y) ans++;
    return ans;
}

int ONline(int x,int y){
    for (auto it : S) if (abs(getY(it,x) - y)<eps) return 1;
    return 0;
}

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]);
    for (int i=1;i<=nrL;i++){
        E[L[i].A.x].push_back({L[i],true});
        E[L[i].A.y].push_back({L[i],false});
    }
    for (int i=0;i<=60000;i++){
        for (auto it : E[i]) if (it.add) S.push_back(it.L);
        for (auto it : M[i]) if (UPline(i,it)%2 || ONline(i,it)) nr++;
        for (auto it : E[i]) if (!it.add) S.push_back(it.L);
    }

    g<<nr;
    return 0;
}