Pagini recente » Cod sursa (job #820548) | Cod sursa (job #1353330) | Cod sursa (job #1860085) | Cod sursa (job #1854686) | Cod sursa (job #1302352)
#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;
}