Cod sursa(job #8043)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 23 ianuarie 2007 19:07:37
Problema Patrate 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 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,range[Nmax][2];
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);
}

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

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

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

	} while (i<j);

	if (i<dr) qsort1(i,dr);
	if (j>st) qsort1(st,j);
}
double absf(double a) {
	if (a<0) return -a;

	return a;
}

int search2(int st,int dr,dot p) {
int m;
	if (st>dr) return 0;

	else {
		m=(st+dr)/2;

		if (absf(v[m].y-p.y)<=EPS) return 1;

		else 
			if (v[m].y<p.y) return search2(m+1,dr,p);

			else return search2(st,m-1,p);
	}
}

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

	if (st>dr) return 0;

	else {
		m=(st+dr)/2;

		if (absf(v[m].x-p.x)<=EPS) 

			return search2(range[m][0],range[m][1],p);
		
		else 
		       	if (v[m].x<p.x) return search(m+1,dr,p);
			
			else return search(st,m-1,p);
	}	
		
}

int main() {
int i,j,k,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;) {
		j=i;
		while (absf(v[j].x-v[i].x)<=EPS && j<=n) ++j;
		
		for (k=i;k<j;++k) {
			range[k][0]=i;
			range[k][1]=j;
		}

		qsort1(i,j-1);

		i=j;
	}

	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;
}