Cod sursa(job #1201668)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 25 iunie 2014 18:53:08
Problema Poligon Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define EPS 0.000001

using namespace std;

double abso(double k)
{
    if(k > 0) return k;
    return -k;
}

struct punct{
    punct(){
        x = y = 0;
    }
    double x,y;
    bool operator <(punct P)
    {
        if(x < P.x) return 1;
        if(x > P.x) return 0;
        return y < P.y;
    }
    bool operator == (punct P)
    {
        if(abso(P.x - x) < EPS &&
           abso(P.y - y) < EPS)
            return 1;
        return 0;
    }
};

struct segment{
    double a,b,c;/// ecuatia
    punct A;
    punct B;
};
int N,M;
vector<punct> v;
vector<segment> s;
punct PS,pc;
int coltz;

segment fa_segment(punct A,punct B)
{
    segment seg;
    seg.A = A;
    seg.B = B;
    seg.a = A.y - B.y;
    seg.b = B.x - A.x;
    seg.c = A.x*(B.y-A.y) + A.y*(A.x-B.x);
    return seg;
}
int det(punct A,punct B,punct C)
{
    return A.x*B.y + B.x*C.y + A.y*C.x -
           A.y*B.x - B.y*C.x - A.x*C.y;
}

void read()
{
    scanf("%d%d",&N,&M);
    punct p;
    for(int i = 1; i <= N; ++i){
        scanf("%lf%lf",&p.x,&p.y);
        v.push_back(p);
    }
    v.push_back(*v.begin());
    for(int i = 1; i <= N; ++i)
        s.push_back(fa_segment(v[i-1],v[i]));
    PS.x = -6613;
    PS.y = -1295;
}

int inters(segment S1,segment S2,segment S3)
{
    if( (S1.B.y - S1.A.y)*(S2.B.x - S2.A.x) ==
        (S2.B.y - S2.A.y)*(S1.B.x - S1.A.x) )
        return 0; /// au aceeasi panta deci sunt paralele si sper ca nu pot coincide ^_^
    punct A,B,C,D;
    A = S1.A;B = S1.B;
    C = S2.A;D = S2.B;
    double X,Y;
    X = (S2.c*S1.b - S1.c*S2.b)/(S1.a*S2.b - S2.a*S1.b);
    Y = (S2.c*S1.a - S1.c*S2.a)/(S1.b*S2.a - S2.b*S1.a);

    if(A.x > B.x) swap(A.x,B.x);
    if(A.y > B.y) swap(A.y,B.y);
    if(C.x > D.x) swap(C.x,D.x);
    if(C.y > D.y) swap(C.y,D.y);

    if(!(A.x - EPS <= X && X <= B.x + EPS &&
       C.x - EPS <= X && X <= D.x + EPS &&
       A.y - EPS <= Y && Y <= B.y + EPS &&
       C.y - EPS <= Y && Y <= D.y + EPS))
        return 0;
    punct interse,p1,p2;
    interse.x = X;interse.y = Y;
    if(!(interse == S2.A || interse == S2.B || interse == S3.A || interse == S3.B))
        return 1;
    if(interse == S2.A) p1 = S2.B;
    else p1 = S1.A;
    if(interse == S3.A) p2 = S3.B;
    else p2 = S3.A;
    if( det(S1.A,S1.B,p1) * det(S1.A,S1.B,p2) < 0)
    {
        ++coltz;
        return 1;
    }
    return 0;
}


bool apartine_segment(punct P,segment S)
{
    if( det(pc,S.A,S.B) != 0 ) return 0;
    if(S.A.x > S.B.x) swap(S.A.x,S.B.x);
    if(S.A.y > S.B.y) swap(S.A.y,S.B.y);
    if(S.A.x - EPS <= P.x && P.x <= S.B.x + EPS &&
       S.A.y - EPS <= P.y && P.y <= S.B.y + EPS)
        return 1;
    return 0;
}

void solve()
{
    int ans = 0;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%lf%lf",&pc.x,&pc.y);
        int nri = 0;
        coltz = 0;
        for(int j = 0; j < N; ++j)
        {
            if(apartine_segment(pc,s[j]))
            {
                nri = 1;
                break;
            }
            if(inters(fa_segment(pc,PS),s[j],s[j+1]) )
                ++nri;
        }
        nri -= coltz;
        if(nri % 2 == 1)
            ++ans;
    }
    printf("%d\n",ans);
}

int main()
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);

    read();
    solve();

    return 0;
}