Cod sursa(job #2500149)

Utilizator bogdi1bogdan bancuta bogdi1 Data 27 noiembrie 2019 12:15:07
Problema Poligon Scor 20
Compilator cpp-64 Status done
Runda guritza Marime 1.44 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct Point
{
    long double x,y;
};
Point polig[805];
bool intersect(Point P1, Point P2, Point P3, Point P4)
{
    long double a1=P1.y-P2.y;
    long double b1=P2.x-P1.x;
    long double c1=P1.x*P2.y-P2.x*P1.y;
    long double a2=P3.y-P4.y;
    long double b2=P4.x-P3.x;
    long double c2=P3.x*P4.y-P4.x*P3.y;
    if(a1*P4.x+b1*P4.y+c1==0)
        return 0;
    if(a1-a2==0)
        return 0;
    if(-b1*a2+a1*b2==0)
        return 0;
    long double y=(c1*a2-a1*c2)/(-b1*a2+a1*b2);
    long double x=((c2-c1)-y*(b1-b2))/(a1-a2);
    if(min(P1.x, P2.x)<=x && x<=max(P1.x,P2.x) && min(P1.y, P2.y)<=y && y<=max(P1.y, P2.y)){
        if(min(P3.x, P4.x)<=x && x<=max(P3.x,P4.x) && min(P3.y, P4.y)<=y && y<=max(P3.y, P4.y))
            return 1;
        else
            return 0;
    }
    else
        return 0;
}
int main()
{   freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    int n,m,i,sol,ans=0,j;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++)
        scanf("%Lf%Lf", &polig[i].x, &polig[i].y);
    for(j=1; j<=m; j++){
        Point P;
        scanf("%Lf%Lf", &P.x, &P.y);
        sol=0;
        for(i=1; i<n; i++)
            sol+=intersect(polig[i], polig[i+1], {-17, -19}, P);
        sol+=intersect(polig[i], polig[1], {-17, -19}, P);
        if(sol%2==1)
            ans++;
    }
    printf("%d", ans);
    return 0;
}