Cod sursa(job #2095652)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 27 decembrie 2017 22:00:46
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

const int nmax = 1500;
const double eps = 1e-3;

struct pct {
    double x, y, lg, u;
} v[nmax + 1], cpy[nmax + 1];

inline double dist2 (pct a, pct b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

inline bool cmp (pct a, pct b) {
    if (fabs(a.lg - b.lg) < eps) {
        return (a.u < b.u);
    } else {
        return a.lg < b.lg;
    }
}

int main () {
    int n;
    fin >> n;

    for (int i = 1; i <= n; ++ i) {
        fin >> v[ i ].x >> v[ i ].y;
    }

    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        int m = 0;
        for (int j = 1; j < i; ++ j) {
            cpy[ ++ m ] = v[ j ];
            cpy[ m ].lg = dist2(v[ i ], v[ j ]);
            cpy[ m ].u = atan2(v[ j ].y - v[ i ].y, v[ j ].x - v[ i ].x);
        }

        sort(cpy + 1, cpy + m + 1, cmp);

        int k = 1;
        for (int j = 1; j <= m; ++ j) {
            while (k < j && cpy[ j ].lg - cpy[ k ].lg > eps) {
                ++ k;
            }

            while (k < j && fabs(cpy[ j ].lg - cpy[ k ].lg) < eps && dist2(cpy[ k ], cpy[ j ]) - cpy[ j ].lg > eps) {
                ++ k;
            }

            if (k < j && fabs(cpy[ j ].lg - cpy[ k ].lg) < eps && fabs(dist2(cpy[ k ], cpy[ j ]) - cpy[ j ].lg) < eps) {
                ++ ans;
            }
        }
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}