Cod sursa(job #2018288)

Utilizator robx12lnLinca Robert robx12ln Data 4 septembrie 2017 12:54:20
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define DIM 1005
using namespace std;
ifstream fin("regiuni.in");
ofstream fout("regiuni.out");
int n, m, sol;
struct dreapta{
    int a;
    int b;
    int c;
} v[DIM];
struct punct{
    int x;
    int y;
};
vector<punct> H[DIM];
int cmp( dreapta D, punct P ){
    int val = D.a * P.x + D.b * P.y + D.c;
    if( val > 0 )
        return 1;
    return 0;
}
int main(){
    fin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        fin >> v[i].a >> v[i].b >> v[i].c;
    }
    sol = 0;
    for( int i = 1; i <= m; i++ ){
        punct P;
        fin >> P.x >> P.y;
        H[sol].push_back( P );
    }
    for( int i = 1; i <= n; i++ ){
        int S = sol;
        for( int j = 0; j <= S; j++ ){
            int ok = 0;
            int gr = 0;
            for( int k = 0; k < H[j].size(); k++ ){
                if( k == 0 ){
                    gr = cmp( v[i], H[j][k] );
                    continue;
                }
                if( cmp( v[i], H[j][k] ) != gr ){
                    if( ok == 0 )
                        ok = 1;
                    H[sol + 1].push_back( H[j][k] );
                    swap( H[j][k], H[j][ H[j].size() - 1 ] );
                    H[j].pop_back();
                    k--;
                }
            }
            sol += ok;
        }
    }
    fout << sol + 1;
    return 0;
}