Cod sursa(job #1156614)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 27 martie 2014 20:03:55
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.03 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 ( (b.x-a.x)*(b.y-a.y)-(x-a.x)*(y-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;
        nrm=0;
        
        for (j = 1; j <= n; ++j){
            
        if (poligon[j].y <= y){
            if (poligon[j + 1].y > y)
                if (det(poligon[j], poligon[j + 1], x, y) > 0)
                    ++nrm;
           }
         else{
            if (poligon[j + 1].y <= y)
                if (det(poligon[j], poligon[j + 1], x, y) < 0)
                    --nrm;
             }
        }
       
        if (nrm!=0) ++sol;  
       }
       
    fout<<sol<<"\n";
    
 return(0);   
}