Cod sursa(job #1153703)

Utilizator andreiagAndrei Galusca andreiag Data 25 martie 2014 17:48:49
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;
const int Nmax = 1505;
const double err = 1e-5;

int N;
double P[2][Nmax];

struct point {
    double dist;
    int index;
};
bool operator< (const point &A, const point &B)
{
    return A.dist < B.dist - err;
}

point A[Nmax];

inline double mdist(int i, int j)
{
    return sqrt((P[0][i] - P[0][j])*(P[0][i] - P[0][j]) +
                (P[1][i] - P[1][j])*(P[1][i] - P[1][j]));
}
int main()
{
    ifstream f ("triang.in");
    ofstream g ("triang.out");
    f >> N;
    for (int i = 0; i < N; i++)
    {
        f >> P[0][i] >> P[1][i];
    }
    
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        int pos = 0;
        for (int j = 0; j < N; j++, pos++)
        {
            if (j == i) { pos--; continue; }
            A[pos].index = j;
            A[pos].dist = mdist(i, j);
        }
        
        sort (A, A + N-1);
        for (int j = 0; j < N-1; j++)
        for (int k = j+1; k < N-1; k++)
        {
            if (A[j].dist + err < A[k].dist) break;
            double d = mdist(A[j].index, A[k].index);
            if (d + err > A[k].dist &&
                d - err < A[k].dist) count++;
        }
    }
    g << count / 3 << '\n';
    return 0;
}