Cod sursa(job #1993029)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 22 iunie 2017 10:34:38
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <cstdio>
using namespace std;
struct punct
{
    double x,y;
} poligon[805],punctDeVerif,centruDeGreutate;
int n,m;

struct dreapta
{
    int a,b,c;
    dreapta()
    {

    }
    dreapta(punct p1,punct p2)
    {
        a=p1.y-p2.y;
        b=p2.x-p1.x;
        c=p1.x*p2.y-p1.y*p2.x;
    }
};
double punctFdreapte(punct p,dreapta d)
{
    double ans=d.a*p.x+d.b*p.y+d.c;
    return ans;
}
punct centrugreutate(punct poligon[])
{
    punct raspuns;
    double sumX;
    double sumY;
    for(int i=1; i<=n; i++)
    {
        sumX+=poligon[i].x;
        sumY+=poligon[i].y;
    }
    raspuns.x=sumX/n;
    raspuns.y=sumY/n;
    return raspuns;
}
bool verificare(punct p)
{
    dreapta dreaptaTMP;
    for(int i=1; i<=n; i++)
    {
        dreaptaTMP=dreapta(poligon[i],poligon[i+1]);
        //printf("%lf  %lf\n",punctFdreapte(centruDeGreutate,dreaptaTMP),punctFdreapte(p,dreaptaTMP));
        if(punctFdreapte(centruDeGreutate,dreaptaTMP)*punctFdreapte(p,dreaptaTMP)<0)
            return false;
    }
    return true;
}
int main()
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    int rasp=0;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%lf%lf",&poligon[i].x,&poligon[i].y);
    }
    poligon[n+1]=poligon[1];
    centruDeGreutate=centrugreutate(poligon);
    for(int i=1; i<=m; i++)
    {
        scanf("%lf%lf",&punctDeVerif.x,&punctDeVerif.y);
        if(verificare(punctDeVerif))
            rasp++;
        //printf("\n");
    }
    printf("%d",rasp);

    return 0;
}