Cod sursa(job #1201656)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 25 iunie 2014 17:29:23
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define EPS 0.00001

using namespace std;

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

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


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

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);
        centroid.x += p.x;
        centroid.y += p.y;
    }
    v.push_back(*v.begin());
    for(int i = 1; i <= N; ++i)
        s.push_back(fa_segment(v[i-1],v[i]));
    centroid.x /= N;
    centroid.y /= N;
    centroid.x = -0.666013;
    centroid.y += -0.666013;
}

int inters(segment S1,segment S2)
{
    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 1;
    return 0;
}

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 solve()
{
    int ans = 0;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%lf%lf",&pc.x,&pc.y);
        int nri = 0;
        for(int i = 0; i < N; ++i)
        {
            if(inters(fa_segment(pc,centroid),s[i]) )
                ++nri;
            if(det(pc,s[i].A,s[i].B) == 0)
            {
                nri = 0;
                break;
            }
        }
        if(nri % 2 == 0)
            ++ans;
    }
    printf("%d\n",ans);
}

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

    read();
    solve();

    return 0;
}