Cod sursa(job #1731218)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 18 iulie 2016 15:56:53
Problema Patrate 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define MOD 8192
using namespace std;

int N,Sol;
float val=(sqrt(5.0)-1)/2;
struct tab
{
	float x,y;
}v[1001];
struct Hash
{
	float x1,y1,x2,y2,p;
};
int f(float x)
{
	float fr=val*x;
	int I=val*x;
	fr=MOD*(fr-I);
	return abs(fr);
}
vector <Hash>H[MOD];
void Add(int i,int j)
{
	int S=f((v[i].x-v[j].x)/(v[i].y-v[j].y));
	Hash C;
	C.p=(v[i].x-v[j].x)/(v[i].y-v[j].y);
	C.x1=v[i].x;
	C.x2=v[j].x;
	C.y1=v[i].y;
	C.y2=v[j].y;
	H[S].push_back(C);
}
bool Nearly(float X,float Y)
{
	int a1=X*10000,a2=Y*10000;
	if(a1==a2||a1==a2-1||a1==a2+1)
		return true;
	else return false;
}
bool Test(Hash X,Hash Y)
{
	float LX=sqrt((X.x1-X.x2)*(X.x1-X.x2)+(X.y1-X.y2)*(X.y1-X.y2)),LY=sqrt((Y.x1-Y.x2)*(Y.x1-Y.x2)+(Y.y1-Y.y2)*(Y.y1-Y.y2));
	if(Nearly(LX,LY)&&Nearly((X.x1+X.x2)/2,(Y.x1+Y.x2)/2)&&Nearly((X.y1+X.y2)/2,(Y.y1+Y.y2)/2))
		return true;
	else return false;
}
bool Search(Hash X)
{
	int S=f(1/X.p);
	for(int i=0;i<H[S].size();i++)
		if(Nearly(H[S][i].p*X.p,-1))
			if(Test(H[S][i],X))
				return true;
	return false;
}
int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%f%f",&v[i].x,&v[i].y);
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
			Add(i,j);
	for(int i=1;i<=MOD;i++)
		for(int j=0;j<H[i].size();j++)
			if(Search(H[i][j]))
				Sol++;
	printf("%d",Sol/2);
	return 0;
}