Cod sursa(job #546399)

Utilizator DaninetDani Biro Daninet Data 4 martie 2011 21:23:42
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<cstdio>

#include<vector>
#include<algorithm>
#include<cmath>

#define eps 1e-4

struct point {
	float x, y;
}aux;

std::vector<point> l;

bool sortFunc(point a, point b) {
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

bool searchFunc(point a, point b) {
	return a.y<b.y;
}
bool searchByX(int a, int b, point val) {
	//printf("!!!!%d", a);
	for(int i = a; i<=b; ++i) {
		if(l[i].x == val.x) return true;
	}
	return false;
}

int cmp(float a, float b) {
	if(a+eps<b)//a > b
		return 1;
	if(b+eps<a) // a < b
		return -1;
	return 0; //a == b
}

bool binary_search(int a, int b, point val) {
	if(a>b) return false;
	//printf("!!!!%d %d\n",a,b);
	int mid = (a+b)/2;
	if(cmp(l[mid].y,val.y) == 1)
		return binary_search(mid+1, b, val);
	else if(cmp(l[mid].y, val.y) == 0)
		return searchByX(a, b, val);
	else	
		return binary_search(a, mid-1, val);
}

bool search(int a, int b, point val) {
	bool t = false;
	for(int i = a; i<=b; ++i) {
		if(fabs(l[i].x - val.x) < eps && fabs(l[i].y - val.y) < eps) t = true;
	}
	return t;
}


float dist(float x1, float y1, float x2, float y2) {
	return sqrtf((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

int main() {
	FILE *f = fopen("patrate3.in", "r");
	FILE *g = fopen("patrate3.out", "w");
	int n;
	fscanf(f, "%d", &n);
	for(int i = 0; i<n; ++i) {
		fscanf(f,"%f %f", &aux.x, &aux.y);
		l.push_back(aux);
	}
	
	int count = 0;

	
	std::sort(l.begin(), l.end(), sortFunc);
	
	for(int i = 0; i<l.size(); ++i) {
		for(int j = i+1; j<l.size(); ++j) {
			
			point center;
			center.x = (l[j].x + l[i].x)/2.0f;
			center.y = (l[j].y + l[i].y)/2.0f;
			float deltax = fabs(l[j].x - center.x);
			float deltay = fabs(l[j].y - center.y);
			point newp;
			newp.x = center.x - deltay;
			newp.y = center.y + deltax;
			printf("%f  ", dist(newp.x, newp.y, center.x, center.y));
			bool ok = true;
			printf("%f %f \n", newp.x, newp.y);
			if(!binary_search(0, l.size()-1, newp)) ok = false;
			if(ok) printf("5sfs");
			newp.x = center.x + deltay;
			newp.y  = center.y - deltax;
			if(ok && binary_search(0, l.size()-1, newp)) {
				count++;
			}
		}
	}
	
	
	printf("%d", count);
	
}