Cod sursa(job #290886)

Utilizator MariusMarius Stroe Marius Data 28 martie 2009 21:42:51
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 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);

vector < pair <double, double> > P;

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

bool operator < (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;
}

bool operator == (const pair <double, double>& a, const pair <double, double>& b) {
    return my_abs(a.first - b.first) < eps && my_abs(a.second - b.second) < eps;
}

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 binary_search(int lo, int hi, const pair <double, double>& p) {
    FOR (i, lo, hi + 1) if (P[i] == p)
        return 1;
    return 0;
/*  while (lo < hi) {
        int mid = (hi + lo) / 2;
        if (P[mid] == p)  return 1;
        if (p < P[mid])
            hi = mid - 1;
        else
            lo = mid + 1;
    }
    return (P[hi] == p) ? 1 : 0;
*/
}

int main(void) {
    ifstream in(iname);
    int n;
    double new_x, new_y, d, a, b, x, y, angle;

    in >> n;
    FOR (i, 0, n)
        in >> x >> y,
        P.push_back( make_pair(x, y) );
    in.close();

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

    int res = 0;

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

    ofstream(oname) << res;

    return 0;
}