Cod sursa(job #1599346)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 13 februarie 2016 19:42:19
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <vector>
#define MOD 1009
#define MOD1 100009
#define MOD2 600037
#define DIM 1002
#define VAL1 43
#define VAL2 47

using namespace std;

int N,M;

struct line{
    int a,b,c;
};

line D[DIM];

struct point{
    int x,y;

    point(int a,int b){
        x=a;
        y=b;
    }
    point(){
        x=y=0;
    }
};

point P;

vector <point> H[MOD];

int which_side(line D,point P){
    return D.a * P.x * 1LL + D.b * P.y * 1LL + D.c > 0;
}

void Hpush(point P){
    int value1 = 0;
    int value2 = 0;

    for(int i=1;i<=N;i++){
        value1 = (value1 * VAL1 * 1LL + which_side(D[i],P))%MOD1;
        value2 = (value2 * VAL2 * 1LL + which_side(D[i],P))%MOD2;
    }

    int loc = value1 % MOD;

    int length = H[loc].size();


    for(int i=0;i<length;i++)
        if(H[loc][i].x==value1 && H[loc][i].y==value2)
            return;

    H[loc].push_back(point(value1,value2));

}

int Sol;

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

int main(){

    fin >> N >> M;

    for(int i=1;i<=N;i++)
        fin >> D[i].a >> D[i].b >> D[i].c;

    for(int i=1;i<=M;i++){
        fin >> P.x >> P.y;
        Hpush(P);
    }

    for(int i=0;i<MOD;i++)
        Sol += H[i].size();

    fout << Sol << "\n";





}