Cod sursa(job #44219)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 30 martie 2007 23:21:45
Problema Regiuni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define nmax 1024
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define sz size()
#define FOR(i,s,d) for(i=(s);i<(d);++i)

pair < pair <int,int> , int > A[nmax];
pair <int,int> P[nmax];
int n,m,sol;
short int H[nmax];
char v[nmax],nw[nmax];

int smn(pair < pair<int,int>,int > A,pair <int,int> P)
{
	return A.f.f*P.f+A.f.s*P.s+A.s>0;
}

int main()
{
	int a,b,c,i,j,k;
	freopen("regiuni.in","r",stdin);
	freopen("regiuni.out","w",stdout);

	scanf("%d %d",&n,&m);
	FOR(i,0,n)
	{
		scanf("%d %d %d",&a,&b,&c);
		A[i]=mp(mp(a,b),c);
	}
	random_shuffle(A,A+n);
	FOR(i,0,m)
	{
		scanf("%d %d",&a,&b);
		P[i]=mp(a,b);		
	}
	random_shuffle(P,P+m);
	sol=1;
	FOR(i,0,m) 
		H[i]=i;
	FOR(i,0,n)
	{
		FOR(j,0,m)
			v[j]=smn(A[i],P[H[j]]);
		FOR(j,0,m)
		{
			a=b=0;
			FOR(k,j,m)
			{
				if(nw[k]&&j!=k)
					break;
				if(v[k])
					a++;
				else
					b++;
			}
			if(a&&b)
			{
				c=b=j+a;
				a=j;
				sol++;
				while(b<m&&!nw[b])
				{
					FOR(a,a,c)
						if(!v[a])
							break;
					FOR(b,b,k)
						if(v[b])
							break;
					if(b<k&&!nw[b])
					{
						swap(H[a],H[b]);
						swap(v[a],v[b]);
					}
					a++,b++;
				}
				nw[c]=1;
			}
			j=k-1;
		}
	}
	printf("%d\n",sol);
	return 0;
}