Cod sursa(job #1991516)

Utilizator Neamtu_StefanStefan Neamtu Neamtu_Stefan Data 17 iunie 2017 11:28:55
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.86 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

int n,m;

struct punct{
    int x,y;
}vf[802],in[60002],punctsuprem;

int f(punct p, punct p1, punct p2)
{
    return ((p.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p.y-p1.y));
}

bool intersectie(punct p1, punct p2, punct p3, punct p4)
{
    return ((f(p1,p3,p4)*f(p2,p3,p4)<0) && (f(p3,p1,p2)*f(p4,p1,p2)<0));
}

int main()
{
    int nr=0;

    fin >> n >> m;

    for (int i=1;i<=n;i++)
        fin >> vf[i].x >> vf[i].y;

    for (int i=1;i<=m;i++)
        fin >> in[i].x >> in[i].y;

    punctsuprem.x=60002;

    for(int i=1;i<=m;i++)
    {
        punctsuprem.y=vf[i].y;
        for (int j=1;j<=n;j++)
            if (intersectie(in[i],punctsuprem,vf[j],vf[j+1])) nr++;
    }

    fout << nr;

    return 0;
}