Cod sursa(job #1293902)

Utilizator jordasIordache Andrei Alexandru jordas Data 16 decembrie 2014 18:49:11
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.67 kb
#include <fstream>
#define xmax 60000

using namespace std;

 ifstream x ("poligon.in");
 ofstream y ("poligon.out");

 struct coord
 {
     int i;
     int j;
 };

 int n,m;
 coord p[802];
 coord point[60001];

 bool intersectie(coord A1, coord B1, coord A2, coord B2)
 {
     int x1=A1.i,x2=B1.i,x3=A2.i,x4=B2.i;
     int y1=A1.j,y2=B1.j,y3=A2.j,y4=B2.j;

     int d=(x1-x2)*(y3-y4)-(x3-x4)*(y1-y2);

     if(d==0)
        return false;

     int xi=((x1*y2-x2*y1)*(x3-x4)-(x3*y4-x4*y3)*(x1-x2))/d;
     int yi=((x1*y2-x2*y1)*(y3-y4)-(x3*y4-x4*y3)*(y1-y2))/d;

     if(xi<min(x1,x2) || xi>max(x1,x2))
        return false;

     if(xi<min(x3,x4) || xi>max(x3,x4))
        return false;

     if(yi<min(y1,y2) || yi>max(y1,y2))
        return false;

     if(yi<min(y3,y4) || yi>max(y3,y4))
        return false;
/*
     y<<xi<<' '<<yi;
     y<<'\n';
*/
     return true;
 }

int main()
{
    int i,j;

    x>>n>>m;

//Citesc punctele poligonului
    for(i=1;i<=n;i++)
       x>>p[i].i>>p[i].j;
    p[n+1]=p[1];

//Citesc punctele de pe plan
    for(i=1;i<=m;i++)
       x>>point[i].i>>point[i].j;

    point[0].i=xmax;

    int nr=0;

    for(i=1;i<=m;i++)
    {
        int nri=0;

        point[0].j=point[i].j;

        for(j=1;j<=n;j++)
        {
            if((point[i].i==p[j].i && point[i].j==p[j].j) || (point[i].i==p[j+1].i && point[i].j==p[j+1].j))
            {
                nri=1;
                break;
            }

            if(intersectie(point[i],point[0],p[j],p[j+1])==true)
               nri++;
        }

        if(nri%2==1)
           nr++;
    }

    y<<nr<<'\n';

    return 0;
}