Cod sursa(job #290869)

Utilizator MariusMarius Stroe Marius Data 28 martie 2009 21:10:59
Problema Triang Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <set>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const char iname[] = "triang.in";
const char oname[] = "triang.out";

#define FOR(i, a, b)  for (int i = (int)(a); i < (int)(b); ++ i)

const double eps = 1e-5;
const double sqrt3 = sqrt(3);

inline double my_abs(const double z) {
    if (z < 0)  return -z;
    return z;
}

bool compare(const pair <double, double>& a, const pair <double, double>& b) {
    if (my_abs(a.first - b.first) < eps) {
        if (my_abs(a.second - b.second) < eps)
            return false;
        else
            return a.second < b.second;
    }
    return a.first < b.first;
}

set < pair <double, double>, bool(*)(const pair <double, double>&, const pair <double, double>&) > S(compare);
vector < pair <double, double> > P;

int find(double a, double b, double x, double y, double angle) {
    double new_x = x * cos(angle) - y * sin(angle) + a;
    double new_y = x * sin(angle) + y * cos(angle) + b;
    return S.find( make_pair(new_x, new_y) ) != S.end();
}

double dist(pair <double, double>& a, pair <double, double>& b) {
    return sqrt( (b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second) );
}

int main(void) {
    ifstream in(iname);
    int n;

    in >> n;
    FOR (i, 0, n) {
        double x, y;
        in >> x >> y;
        S.insert( make_pair(x, y) );
        P.push_back( make_pair(x, y) );
    }
    in.close();

    sort(P.begin(), P.end());

    int res = 0;

    FOR (i, 0, n) FOR (j, i + 1, n) {
        double d = dist(P[i], P[j]);
        if (P[i].first == P[j].first) {
            double new_x = d * sqrt3 / 2;
            double new_y = d / 2;
            res += S.find( make_pair(new_x, new_y) ) != S.end();
            new_x = -new_x;
            res += S.find( make_pair(new_x, new_y) ) != S.end();
        }
        else {
            double angle = atan2(P[j].second - P[i].second, P[j].first - P[i].first);
            double a = P[i].first, b = P[i].second;
            double x = d / 2, y = d * sqrt3 / 2;
            res += find(a, b, x, y, angle);
            res += find(a, b, x, -y, angle);
        }
    }

    ofstream(oname) << res / 3;

    return 0;
}