Cod sursa(job #585292)

Utilizator maritimCristian Lambru maritim Data 28 aprilie 2011 20:43:37
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define er 0.0000001

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

dreapta A[500100];
dreapta P[1001];
int N;
int nr;
int MAX;
double ct = 0;

int compara (double a,double b)
{
    if (fabs (a-b)<=0.00001)
        return 1;
    return 0;
}

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++)
		{
			int semn;
			A[++nr].m = (P[i].d-P[j].d)/(P[i].m-P[j].m);
			A[nr].d = 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));
			A[nr].x = (P[i].m+P[j].m)/2;
			A[nr].y = (P[i].d+P[j].d)/2;
		}
}

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(compara(A[j].d,A[i].d))
		{
			if(compara(A[i].m*A[j].m,-1) && compara(A[i].x,A[j].x) && compara(A[i].y,A[j].y))
				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;
}