Cod sursa(job #1156587)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 27 martie 2014 19:50:12
Problema Poligon Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.08 kb
#include<fstream>
#define ll long long
using namespace std;
typedef struct { ll x,y; } punct;
punct poligon[805], multime[60005];
ll i,j,n,m,sol,x,y,ok,nrm;

ll det( punct a, punct b, int x, int y ) {
    return ( a.x*b.y + y*b.x + x*a.y - x*b.y - y*a.x - b.x*a.y );
}

int main(void) {
    ifstream fin("poligon.in");
    ofstream fout("poligon.out");
    
    fin>>n>>m;
    for (i=1; i<=n; ++i) fin>>poligon[i].x>>poligon[i].y;
    poligon[n+1]=poligon[1];
    
    for (i=1; i<=m; ++i) {
        fin>>x>>y;
        ok=nrm=0;
        
        for (j=1; j<=n; ++j)
        if ( y>poligon[j].y&&y<=poligon[j+1].y ) {
            int d=det(poligon[j], poligon[j+1], x,y);
            if ( d < 0) ++nrm;
                else if (d==0) ok=1;
            }
        else if (y>=poligon[j+1].y&&y<poligon[j].y) {
              int d=det(poligon[j], poligon[j+1], x,y);
              if ( d > 0) --nrm;
               else if ( d==0 ) ok=1;
             }
            
        if (nrm!=0||ok==1) ++sol;
        
        }
    
    fout<<sol<<"\n";
    
 return(0);   
}