Cod sursa(job #1302352)

Utilizator stefanzzzStefan Popa stefanzzz Data 26 decembrie 2014 20:28:51
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <math.h>
#include <vector>
#define MAXN 1505
#define PREC 10000
#define EPS 0.0001
#define MAXHASH1 666013
#define MAXHASH2 109279
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");

inline bool is_equal(double &a, double &b){
	return fabs(a - b) < EPS;
};

int n, sol;
pair<double, double> v[MAXN];
vector< pair<double, double> > v_hash[MAXHASH2 + 20];

inline void rotate(pair<double, double> &p, double u){
	double x = p.first, y = p.second;
	p.first = x * cos(u) - y * sin(u);
	p.second = x * sin(u) + y * cos(u);
}

inline int hash_value(pair<double, double> x){
	int h1 = ((int)(x.first * PREC + 0.5) + 1LL * MAXHASH1 * MAXHASH1) % MAXHASH1;
	int h2 = ((int)(x.second * PREC + 0.5) + 1LL * MAXHASH1 * MAXHASH1) % MAXHASH1;

	return (1LL * h1 * MAXHASH1 + h2) % MAXHASH2;
}

inline bool is_in_hash(pair<double, double> x){
	int h_val = hash_value(x);
	int i;
	//g << "is_in " << x.first << ' ' << x.second << ' ' << hash_value(x) << '\n'; 
	for(i = 0; i < v_hash[h_val].size(); i++)
		if(is_equal(x.first, v_hash[h_val][i].first) && is_equal(x.second, v_hash[h_val][i].second))
			return 1;
	return 0;
}

inline void solve(pair<double, double> &p1, pair<double, double> &p2){
	pair<double, double> p2t = make_pair(p2.first - p1.first, p2.second - p1.second);
	pair<double, double> p3, aux;
	double u = atan2(p2t.second, p2t.first);
	
	rotate(p2t, -u);
		
	p3.first = p2t.first / 2;
	p3.second = sqrt(3 * (p2t.first * p2t.first + p2t.second * p2t.second)) / 2;
	aux = p3;

	rotate(p3, u);
	p3.first += p1.first; p3.second += p1.second;
	
	if(is_in_hash(p3))
		sol++;
	
	p3 = aux;
	p3.second = -p3.second;
	
	rotate(p3, u);
	p3.first += p1.first; p3.second += p1.second;
	
	if(is_in_hash(p3))
		sol++;
}

int main(){
	int i, j;

	f >> n;
	for(i = 1; i <= n; i++){
		f >> v[i].first >> v[i].second;
		for(j = 1; j < i; j++)
			solve(v[i], v[j]);
		//g << v[i].first << ' ' << v[i].second << ' ' << hash_value(v[i]) << '\n';
		v_hash[hash_value(v[i])].push_back(v[i]);
	}

	g << sol / 2 << '\n';

	f.close();
	g.close();
	return 0;
}