Cod sursa(job #37601)

Utilizator cretuMusina Rares cretu Data 25 martie 2007 11:21:13
Problema Regiuni Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 1.86 kb
#include <fstream>
#define MAX 1001

using namespace std;

int n, m;
int g[MAX], h[MAX];
bool u[MAX];
struct dreapta{
    int a, b, c;
} d[MAX];

struct punct{
    int x, y;
} p[MAX];       

int Check(int x1, int y1);
void Union(int x, int y);  
int Find(int x);

int main()
{
    int i, j, nr = 0, ok, x;
    ifstream fin("regiuni.in");
    fin >> m >> n;
    for (i = 1; i <= m; i++)    
        fin >> d[i].a >> d[i].b >> d[i].c;
    for (i = 1; i <= n; i++)
    {
        fin >> p[i].x >> p[i].y;
        g[i] = i;
        h[i] = 0;
    }
    fin.close();

    for (i = 1; i <= n; i++)
    {
        ok = 1;
        memset(u, 0, sizeof(u));
        for (j = 1; j <= n && ok; j++)    
            if (i != j)
            {
                 x = Find(j);
                 if (u[x]) continue;
                 if (Check(i, x))   
                 {
                     ok = 0;
                     Union(i, x);            
                 }
                 else u[x] = 1;
            }
    }

    ofstream fout("regiuni.out");
    memset(u, 0, sizeof(u));
    for (i = 1; i <= n; i++)
    {
        x = Find(i);
        if (!u[x])
        {
           u[x] = 1;
           nr++;          
        }    
    }
    fout << nr << "\n";
    fout.close();
}

int Check(int x1, int y1)
{
    int i, aux1, aux2;
    for (i = 1; i <= m; i++)    
    {
        aux1 = d[i].a*p[x1].x + d[i].b*p[x1].y + d[i].c;
        aux2 = d[i].a*p[y1].x + d[i].b*p[y1].y + d[i].c;
        if ((aux1 > 0 && aux2 < 0) || (aux1 < 0 && aux2 > 0)) return 0;
    }
    return 1;
}

void Union(int x, int y)  
{
    x = Find(x);
        
    if (x == y) return;
    
	if (h[x] > h[y]) g[y] = x;
	else
	{
	    g[x] = y;
	    if (h[x] == h[y]) ++h[y];
	}
}

int Find(int x)   
{
	if ( x != g[x] ) g[x] = Find(g[x]);
	return g[x];
}