Cod sursa(job #2073492)

Utilizator victoreVictor Popa victore Data 23 noiembrie 2017 11:26:49
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<bits/stdc++.h>

using namespace std;

const int NMAX = 805;
const int MMAX = 60005;
const int INF = 1e9;
const double eps = 1e-9;

int n,m;

struct point
{
    double x,y;
}punct[NMAX],Q;

struct PunctCuPanta
{
    double panta;
    point p;
}Sorted[NMAX];

inline double cp(point p1 , point p2 , point p3)
{
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}

inline int ccw(point p1,point p2,point p3)
{
    double a = cp(p1,p2,p3);
    if(a > 0)
        return 1;
    if(a == 0)
        return 0;
    return -1;
}

inline bool InTriangle(point p1 , point p2 , point p3 , point q)
{
    double A1 , A2 , A3 , At;
    A1 = fabs( cp(p1,p2,q) );
    A2 = fabs( cp(p2,p3,q) );
    A3 = fabs( cp(p3,p1,q) );
    At = fabs( cp(p1 , p2 , p3) );

    return( fabs( At - (A1 + A2 + A3) ) < eps );
}

inline bool cmp(const PunctCuPanta &s1 , const PunctCuPanta &s2)
{
    return s1.panta - s2.panta <= -eps;
}

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

    int j,i;

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;++i)
        scanf("%lf%lf",&punct[i].x,&punct[i].y);

    //aleg punct[1]

    for(i=2;i<=n;++i)
    {
        Sorted[i].p = punct[i];
        if(punct[i].x == punct[1].x)
            Sorted[i].panta = INF;
        else
            Sorted[i].panta = (punct[i].y - punct[1].y)/(punct[i].x - punct[1].x);
    }

    sort(Sorted+2 , Sorted+n+1 , cmp);

    int aux,step;
    double ma;

    for(aux = 1; aux < n ; aux<<=1);

    int cnt = 0;

    for(j=1;j<=m;++j)
    {
        scanf("%lf%lf",&Q.x,&Q.y);
        if(Q.x == punct[1].x)
            ma = INF;
        else
            ma = (Q.y - punct[1].y)/(Q.x - punct[1].x);

        for(step = aux , i = 3 ; step ; step>>=1)
            if(i+step <= n && ma - Sorted[i + step].panta > -eps)
                i+=step;

        if( InTriangle(punct[1] , Sorted[i-1].p , Sorted[i].p , Q) )
            cnt++;

    }

    printf("%d",cnt);

}