Cod sursa(job #1020314)

Utilizator ELHoriaHoria Cretescu ELHoria Data 1 noiembrie 2013 21:50:19
Problema Triang Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstdio>
#include <math.h>
#include <functional>
#include <vector>
#define pdd pair<double,double>
#define M_PI  3.14159265358979323846
#define eps 1e-4
#define x first
#define y second

using namespace std;

const double s60 = sin(60 * M_PI / 180.0);    
const double c60 = cos(60 * M_PI / 180.0);
const double offset = 50000.0;
const int nmax = 1502;
const int mod = 666013;
int n;
pdd v[nmax];

inline pair<pdd,pdd> getPoints(pdd a,pdd b) {
	return make_pair( 
		make_pair(c60 * (a.x - b.x) - s60 * (a.y - b.y) + b.x,
				  s60 * (a.x - b.x) + c60 * (a.y - b.y) + b.y),
		make_pair(c60 * (a.x - b.x) + s60 * (a.y - b.y) + b.x,
				  -	s60 * (a.x - b.x) + c60 * (a.y - b.y) + b.y ));
}

inline double dist(pdd a,pdd b) {
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}


vector< pdd > h[mod];//4 decimals precison
inline void insert(pdd p) {
	int num1 = static_cast<int>(p.x*10000);
	int num2 = static_cast<int>(p.y*10000);
	int hash = 1ll*num1*num2%mod;
	h[hash].push_back(p);
}

inline bool isEqual(const double &a,const double &b) {
	return fabs(b - a) < eps;
}

inline bool findPoint(pdd p) {
	int num1 = static_cast<int>(p.x*10000);
	int num2 = static_cast<int>(p.y*10000);
	int hash = 1ll*num1*num2%mod;
	for(const auto &val : h[hash]) {
		if(isEqual(val.x,p.x) && isEqual(val.y,p.y)) {
			return true;
		}
	}
	return false;
}

inline void readData() {
	scanf("%d",&n);
	for(int i = 0;i < n;i++) {
		scanf("%lf %lf",&v[i].x,&v[i].y);
	}
}

inline int solve() {
	int ret = 0;
	for(int i = 0;i < n;i++) {
		v[i].x += offset;
		v[i].y += offset;
		insert(v[i]);
	}
	for(int i = 0;i < n;i++) {
		for(int j = i + 1;j < n;j++) {
			pair< pdd ,pdd > points = getPoints(v[i],v[j]);
			ret += findPoint(points.x) + findPoint(points.y);
		}
	}
	return ret;
}

int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
	readData();
	printf("%d\n",solve());
    return 0;
}