Cod sursa(job #546229)

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

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

#define eps 1e-5

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 searchByY(int a, int b, point val) {
	printf("!!!!%d", a);
	for(int i = a; i<=b; ++i) {
		if(l[i].y == val.y) return true;
	}
	return false;
}

bool binary_search(int a, int b, point val) {
	if(a>b) return false;
	printf("!!!!%d", b);
	int mid = (a+b)/2;
	if(val.x>l[mid].x)
		return binary_search(mid+1, b, val);
	else if(val.x==l[mid].x)
		return true;//searchByY(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;
}

bool searchFunc(point a, point b) {
	if(a.x<b.x) return true;
	return false;
}

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);
	
	std::vector<point>::iterator it1, it2;
	
	it1 = l.begin();
	while(it1!=l.end()) {
		it2 = it1;
		++it2;
		while(it2!=l.end()) {
			//printf("x: %f %f\n", it1->x, it1->y); 
			//printf("y: %f %f\n", it2->x, it2->y); 
			point center;
			center.x = (it2->x + it1->x)/2.0f;
			center.y = (it2->y + it1->y)/2.0f;
			//printf("center: %f %f\n", center.x, center.y); 
			float deltax = fabs(it2->x - center.x);
			float deltay = fabs(it2->y - center.y);
			point newp;
			newp.x = center.x - deltay;
			newp.y = center.y + deltax;
			//printf("delta: %f %f\n", deltax, deltay);
			printf("A: %f %f\n", newp.x, newp.y);
			bool ok = true;
			
			if(!search(0, l.size()-1, newp)) ok = false;
			newp.x = center.x + deltay;
			newp.y  = center.y - deltax;
			if(ok && search(0, l.size()-1, newp)) {
				count++;
			}
			++it2;
		}
		
		++it1;
	}
	fprintf(g,"%d", count);
	
}