Cod sursa(job #8039)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 23 ianuarie 2007 18:54:18
Problema Patrate 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#include<math.h>
#define fin  "patrate3.in"
#define fout "patrate3.out"
#define Nmax 1001
#define EPS 0.0001
struct dot { double x; double y; };
int n,sol;
dot v[Nmax];
FILE *in,*out;

void qsort(int st,int dr) {
int i,j;
dot m;
	i=st; j=dr;

	m=v[(i+j)/2];

	do {
		while (v[i].x<m.x) ++i;
		while (v[j].x>m.x) --j;
		if (i<=j) {
			dot aux;
			aux=v[i]; v[i]=v[j]; v[j]=aux;
			++i; --j;
		}

	} while (i<j);

	if (i<dr) qsort(i,dr);
	if (j>st) qsort(st,j);
}

double absf(double a) {
	if (a<0) return -a;

	return a;
}

int search(int st,int dr,dot p) {
int i,m;

	for (i=1;i<=n;++i) 
		if ( absf(p.x-v[i].x)<=EPS && absf(p.y-v[i].y)<=EPS) return 1;

	return 0;
		
}

int main() {
int i,j,good;
dot mijl,p1,p2;
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%i",&n);

	for (i=1;i<=n;++i)
		fscanf(in,"%lf%lf",&v[i].x,&v[i].y);

	qsort(1,n);

	for (i=1;i<n;++i) 
	for (j=i+1;j<=n;++j) {
		
		good=1;
		
		mijl.x=(v[i].x+v[j].x)*0.5;
		mijl.y=(v[i].y+v[j].y)*0.5;
		
		p1.x=mijl.x - (v[i].y-mijl.y);
		p1.y=mijl.y + (v[i].x-mijl.x);
		
		p2.x=mijl.x - (v[j].y-mijl.y);
		p2.y=mijl.y + (v[j].x-mijl.x);
		
		if (!search(1,n,p1)) good=0;
		if (!search(1,n,p2)) good=0;
		
		if (good) sol++;
		
			
	}

	sol/=2;

	fprintf(out,"%i\n",sol);

	fclose(in); fclose(out);

	return 0;
}