Cod sursa(job #3138789)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 22 iunie 2023 13:07:51
Problema Overlap Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
#include<queue>
#include<bitset>
const int NMAX=805;

struct pos
{
	int x, y, idx;

	friend bool operator<(pos a, pos b)
	{
		return a.x<b.x || (a.x==b.x && a.y<b.y);
	}

	friend bool operator==(pos a, pos b)
	{
		return a.x==b.x && a.y==b.y;
	}
};

struct el
{
	int idx, inDeg;

	friend bool operator<(el a, el b)
	{
		return a.inDeg>b.inDeg;
	}
};

inline pos apply(pos p, int k)
{
	pos ans=p;
	switch(k)
	{
	case 1:
		ans.x=p.y;
		ans.y=-p.x;
		break;
	case 2:
		ans.x=-p.x;
		ans.y=-p.y;
		break;
	case 3:
		ans.x=-p.y;
		ans.y=p.x;
	}
	return ans;
}

inline pos apply(pos p, int k, pos off)
{
	pos ans=apply(p, k);
	ans.x+=off.x;
	ans.y+=off.y;
	return ans;
}

int N, hN;
int inDeg[NMAX], coresp[NMAX];
pos v[NMAX];
std::bitset<NMAX> side, matched;

inline int find(pos p)
{
	int l=0, r=N-1, mid;

	do
	{
		mid=(l+r)>>1;
		if(v[mid]==p)
			return mid;
		if(v[mid]<p)
			l=mid+1;
		else
			r=mid-1;
	}while(l<=r);

	return -1;
}

bool tryOut(int k, pos off)
{
	int i, j, matches=0;
	pos ans;
	std::priority_queue<el> pq;

	for(i=0;i<N;++i)
		inDeg[i]=0;

	for(i=0;i<N;++i)
	{
		ans=apply(v[i], k, off);
		j=find(ans);
		if(j!=-1 && i!=j)
		{
			++inDeg[j];
			coresp[i]=j;
			++matches;
		}
		else
			coresp[i]=-1;
	}

	if(matches<hN)
		return 0;

	matches=0;
	matched.reset();

	el e;

	for(i=0;i<N;++i)
	{
		e.idx=i;
		e.inDeg=inDeg[i];
		pq.push(e);
	}

	do
	{
		e=pq.top();
		pq.pop();

		if(!matched[e.idx])
		{
			if(coresp[e.idx]==-1 || matched[coresp[e.idx]])
				return 0;
			side[v[e.idx].idx]=0;
			side[v[coresp[e.idx]].idx]=1;
			matched[e.idx]=1;
			matched[coresp[e.idx]]=1;
			++matches;
		}
	}while(!pq.empty());

	return matches==hN;
}

int main()
{
	FILE* f=fopen("overlap.in", "r"), *g=fopen("overlap.out", "w");
	//FILE* f=stdin, *g=stdout;
	int i, k;
	pos aux, off;

	fscanf(f, "%d", &N);
	hN=N>>1;
	for(i=0;i<N;++i)
	{
		fscanf(f, "%d%d", &v[i].x, &v[i].y);
		v[i].idx=i;
	}
	std::sort(v, v+N);

	for(i=1;i<N;++i)
		if(v[i]==v[i-1])
		{
			for(i=aux.idx=0;i<N || !aux.idx;++i);
		}

	for(k=0;k<4;++k)
	{
		aux=apply(v[0], k);
		for(i=1;i<N;++i)
		{
			off.x=v[i].x-aux.x;
			off.y=v[i].y-aux.y;

			if(tryOut(k, off))
			{
				i=N;
				k=4;
			}
		}

		if(k!=4)
		{
			for(i=1;i<N;++i)
			{
				aux=apply(v[i], k);
				off.x=v[0].x-aux.x;
				off.y=v[0].y-aux.y;

				if(tryOut(k, off))
				{
					i=N;
					k=4;
				}
			}
		}
	}

	for(i=0;i<N;++i)
		if(side[i])
			fprintf(g, "2\n");
		else
			fprintf(g, "1\n");

	fclose(f);
	fclose(g);
	return 0;
}