Cod sursa(job #3137708)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 14 iunie 2023 17:21:57
Problema Overlap Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=805;

struct pos
{
	int x, y;
};

struct trans
{
	int k, xoff, yoff, i, j;

	friend bool operator<(trans a, trans b)
	{
		return a.k<b.k || a.k==b.k && a.xoff<b.xoff || a.k==b.k && a.xoff==b.xoff && a.yoff<b.yoff;
	}
};

int N;
pos v[NMAX];
int cnt;
trans t[NMAX*NMAX];

trans getTrans(int i, int j, int k)
{
	trans t;
	t.i=i;
	t.j=j;
	t.k=k;

	pos ref;
	switch(k)
	{
	case 0:
		ref=v[i];
		break;
	case 1:
		ref.x=-v[i].y;
		ref.y=v[i].x;
		break;
	case 2:
		ref.x=-v[i].x;
		ref.y=-v[i].y;
		break;
	case 3:
		ref.x=v[i].y;
		ref.y=-v[i].x;
	}

	t.xoff=v[j].x-ref.x;
	t.yoff=v[j].y-ref.y;

	return t;
}

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

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%d%d", &v[i].x, &v[i].y);

	for(i=0;i<N;++i)
		for(j=0;j<N;++j)
			if(i!=j)
			{
				t[cnt++]=getTrans(i, j, 0);
				t[cnt++]=getTrans(i, j, 1);
				t[cnt++]=getTrans(i, j, 2);
				t[cnt++]=getTrans(i, j, 3);
			}

	std::sort(t, t+cnt);

	for(i=curr=1;i<cnt;++i)
	{
		if(t[i].k==t[i-1].k && t[i].xoff==t[i-1].xoff && t[i].yoff==t[i-1].yoff)
		{
			if(++curr==N/2)
			{
				for(j=i-curr;j<=i;++j)
					v[t[j].i].x=1,
					v[t[j].j].x=2;
				i=cnt;
			}
		}
		else
			curr=1;
	}

	for(i=0;i<N;++i)
		fprintf(g, "%d\n", v[i].x);

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