Cod sursa(job #1020331)

Utilizator ELHoriaHoria Cretescu ELHoria Data 1 noiembrie 2013 22:17:05
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <functional>
#include <vector>
#define pdd pair<double,double>
#define M_PI  3.14159265358979323846
 
#define x first
#define y second
 
using namespace std;
 
const double eps = 1e-3;
const double s60 = sin(M_PI / 3.0);   
const double c60 = cos(M_PI / 3.0);
const int nmax = 1502;
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 int comp(const pdd &a,const pdd &b) {
	if(fabs(a.x - b.x) < eps) {
		if(fabs(a.y - b.y) < eps) return 0;
		return a.y < b.y ? -1 : 1;
	}
	return a.x < b.x ? -1 : 1;
}
 
inline void readData() {
    scanf("%d",&n);
    for(int i = 0;i < n;i++) {
        scanf("%lf %lf",&v[i].x,&v[i].y);
    }
}
 
inline bool search(pdd p) {
    int pos = 0;
    for(int step = 1<<11;step > 0;step >>= 1) {
        if(pos + step < n) {
            if(comp(p,v[pos]) <= 0) {
                pos += step;
            }
        }
    }
     
    return (comp(p,v[pos]) == 0);
}
 
inline int solve() {
    int ret = 0;
    sort(v,v + n);
    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 += search(points.x) +search(points.y);
        }
    }
    return ret;
}
 
int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    readData();
    printf("%d\n",solve());
    return 0;
}