Cod sursa(job #827563)

Utilizator toranagahVlad Badelita toranagah Data 2 decembrie 2012 11:50:08
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
#define x first
#define y second
const int MAX_N = 1510;
const double sin60 = sqrt(3.0) / 2;
const double cos60 = 1.0 / 2;
const double EPSILON = 1e-3;
pair<double, double> points[MAX_N];
int N;
int sol;

void read(), solve(), print();
int binary_search(double val);

int main() {
    read();
    solve();
    print();
    return 0;
}

bool cmp(pair<double, double> a, pair<double, double> b) {
    return ((b.x - a.x > EPSILON) || ((fabs(b.x - a.x) < EPSILON) && (b.y -a.y > EPSILON)));
}

void read() {
    ifstream fin("triang.in");
    fin >> N;
    for (int i = 1; i <= N; ++i) {
        fin >> points[i].x >> points[i].y;
    }
}

int binary_search(pair<double, double> p) {
    int lo = 1, hi = N, mid;
    while (lo + 1 < hi) {
        mid = lo + (hi - lo) / 2;
        if (fabs(points[mid].x - p.x) < EPSILON && (fabs(points[mid].y - p.y) < EPSILON)) {
            return mid;
        } else if (cmp(points[mid], p)) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return 0;
}

void solve() {
    sort(points + 1, points + N + 1, cmp);
    double x, y;
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            x = points[i].x + (points[j].x - points[i].x) * cos60 - (points[j].y - points[i].y) * sin60;
            y = points[i].y + (points[j].y - points[i].y) * cos60 + (points[j].x - points[i].x) * sin60;
            if (binary_search(make_pair(x, y)) > j) ++sol;
            x = points[i].x + (points[j].x - points[i].x) * cos60 + (points[j].y - points[i].y) * sin60;
            y = points[i].y + (points[j].y - points[i].y) * cos60 - (points[j].x - points[i].x) * sin60;
            if (binary_search(make_pair(x, y)) > j) ++sol;
        }
    }
}

void print() {
    ofstream fout("triang.out");
    fout << sol;
}