Cod sursa(job #1990807)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 13 iunie 2017 18:33:01
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <cstdio>
using namespace std;
struct punct
{
    int x,y;
} poligon[804],punctDeVerif;
int n,nrp,m[3][3];

int determinat(int a[3][3])
{
    int f=a[0][0]*a[1][1]*a[2][2]+a[1][0]*a[2][1]*a[0][2]+a[2][0]*a[0][1]*a[1][2];
    int s=a[0][2]*a[1][1]*a[2][0]+a[1][2]*a[2][1]*a[0][0]+a[2][2]*a[0][1]*a[1][0];
    return f-s;
}
void constructMatrice(punct p1,punct p2,punct p3,int matrice[3][3])
{
    for(int i=0; i<3; i++)
        matrice[i][0]=1;

    matrice[0][1]=p1.x;
    matrice[0][2]=p1.y;

    matrice[1][1]=p2.x;
    matrice[1][2]=p2.y;

    matrice[2][1]=p3.x;
    matrice[2][2]=p3.y;
}
int sgn(int x)
{
    if(x>0)
        return 1;
    if(x<0)
        return -1;
    return 0;
}
bool verif(punct p)
{
    constructMatrice(poligon[1],poligon[2],punctDeVerif,m);
    int prevSgn=sgn(determinat(m));
    for(int j=2; j<=n; j++)
    {
        constructMatrice(poligon[j],poligon[j+1],punctDeVerif,m);
        if(sgn(determinat(m)))
            if(prevSgn!=sgn(determinat(m)))
                return false;
    }
    return true;
}
int main()
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    int raspuns=0;
    scanf("%d",&n);
    scanf("%d",&nrp);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&poligon[i].x,&poligon[i].y);
    }
    poligon[n+1]=poligon[1];
    for(int i=1; i<=nrp; i++)
    {
        scanf("%d%d",&punctDeVerif.x,&punctDeVerif.y);
        if(verif(punctDeVerif))
            raspuns++;
    }
    printf("%d",raspuns);
    return 0;
}