Cod sursa(job #949778)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 14 mai 2013 21:56:47
Problema Frac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 1510;
const double sin60 = sqrt(3.0) / 2;
const double cos60 = 1.0 / 2;
const double EPSILON = 1e-3;
struct punct {double x, y;} p[MAX_N];
int N;
int sol;
void read(), solve(), print();
int main() {
    read();
    solve();
    print();
    return 0;
}
 
bool cmp(punct a, punct 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 >> p[i].x >> p[i].y;
    }
}
 
bool binary_search(int lo, int hi, punct pct) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (fabs(p[mid].x - pct.x) < EPSILON && fabs(p[mid].y - pct.y) < EPSILON) {
            return true;
        } else if (cmp(p[mid], pct)) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return false;
}
 
void solve() {
    sort(p + 1, p + N + 1, cmp);
    punct pct;
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            pct.x = p[i].x + (p[j].x - p[i].x) * cos60 - (p[j].y - p[i].y) * sin60;
            pct.y = p[i].y + (p[j].y - p[i].y) * cos60 + (p[j].x - p[i].x) * sin60;
            if (binary_search(j + 1, N, pct)) ++sol;
            pct.x = p[i].x + (p[j].x - p[i].x) * cos60 + (p[j].y - p[i].y) * sin60;
            pct.y = p[i].y + (p[j].y - p[i].y) * cos60 - (p[j].x - p[i].x) * sin60;
            if (binary_search(j + 1, N, pct)) ++sol;
        }
    }
}
 
void print() {
    ofstream fout("triang.out");
    fout << sol;
}