Cod sursa(job #1153635)

Utilizator tudorv96Tudor Varan tudorv96 Data 25 martie 2014 17:03:39
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;

ifstream fin ("triang.in");
ofstream fout ("triang.out");

const int N = 1505;
const double eps = 1e-3, rad3 = 1.73205080;

int n, sol;
pair <double, double> v[N];

double abs(double x) {
    return x > -x ? x : -x;
}

bool bs(pair <double, double> point) {
    int poz = 0;
    for (int step = 1 << 11; step; step >>= 1)
        if (abs (v[poz].first - point.first) < eps) {
            if (poz + step < n && v[poz+step].second < point.second + eps && v[poz].first == v[poz+step].first)
                poz += step;
        }
        else
            if (poz + step < n && v[poz+step].first < point.first + eps)
                poz += step;
    if (abs (v[poz].first - point.first) < eps && abs (v[poz].second - point.second) < eps)
        return 1;
    return 0;
}

int main() {
    fin >> n;
    for (int i = 0; i < n; ++i)
        fin >> v[i].first >> v[i].second;
    sort (v, v + n);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            pair <double, double> point;
            point.first = (v[i].first + v[i].second * rad3 + v[j].first - v[j].second * rad3) / 2.0;
            point.second = (-v[i].first * rad3 + v[i].second + v[j].first * rad3 + v[j].second) / 2.0;
            //cout << v[i].first << " " << v[i].second << " & " << v[j].first << " " << v[j].second << " -- " << point.first << " " << point.second << "\n";
            sol += bs(point);
            point.first = (v[i].first - v[i].second * rad3 + v[j].first + v[j].second * rad3) / 2.0;
            point.second = (v[i].first * rad3 + v[i].second - v[j].first * rad3 + v[j].second) / 2.0;
            //cout << v[i].first << " " << v[i].second << " & " << v[j].first << " " << v[j].second << " -- " << point.first << " " << point.second << "\n";
            sol += bs(point);
        }
    fout << sol / 3;

}