Cod sursa(job #585269)

Utilizator maritimCristian Lambru maritim Data 28 aprilie 2011 19:51:22
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<math.h>

typedef struct 
{
	double m;
	double d;
} dreapta;

dreapta A[500100];
dreapta P[1001];
int N;
int nr;
int MAX;

void citire(void)
{
	FILE *f = fopen("patrate3.in","r");
	
	fscanf(f,"%d",&N);
	for(int i=1;i<=N;i++)
		fscanf(f,"%lf %lf",&P[i].m,&P[i].d);
	
	fclose(f);
}

void prelucrare(void)
{
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
		{
			A[++nr].m = (double)(P[i].d-P[j].d)/(P[i].m-P[j].m);
			A[nr].d = (double)sqrt((P[i].d-P[j].d)*(P[i].d-P[j].d) + (P[i].m-P[j].m)*(P[i].m-P[j].m));
		}
}

int poz(int li,int ls)
{
	dreapta a = A[(li+ls)/2];
	A[(li+ls)/2] = A[li];
	A[li] = a;
	int i1 = 0;
	int j1 = -1;
	int c = 0;
	while(li<ls)
	{
		if((double)A[li].d>(double)A[ls].d)
		{
			a = A[li];
			A[li] = A[ls];
			A[ls] = a;
			c = -i1;
			i1 = -j1;
			j1 = c;
		}
		li += i1;
		ls += j1;
	}
	return li;
}

void quicksort(int li,int ls)
{
	if(li<ls)
	{
		int k = poz(li,ls);
		quicksort(li,k-1);
		quicksort(k+1,ls);
	}
}

void solve(void)
{
	int i=1;
	while(i<=nr)
	{
		int j=i+1;
		while(A[j].d == A[i].d)
		{
			if(int(A[j].m*A[i].m) == -1)
				MAX ++;
			j ++;
		}
		i ++;
	}
}

int main()
{
	FILE *g = fopen("patrate3.out","w");
	
	citire();
	prelucrare();
	quicksort(1,nr);
	solve();
	fprintf(g,"%d",MAX);
	
	fclose(g);
	return 0;
}