Cod sursa(job #1744910)

Utilizator antanaAntonia Boca antana Data 20 august 2016 18:37:46
Problema Triang Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 1500
#define EPS 0.0001

struct segments{
    double dist;
    int p;
}a[MAXN+1][MAXN+1];

struct points{
    double x, y;
}v[MAXN+1];

int n, ans, k;

inline double distanta(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

bool cmp(const segments &a, const segments &b)
{
    return ((a.dist - b.dist) < 0);
}

inline double abs1(double a)
{
    if(a<0)
        return a*-1;
    return a;
}

int main()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);

    int st, dr, m, f, point;
    double d;

    scanf("%d", &n);

    for(int i=1;i<=n;++i)
        scanf("%lf%lf", &v[i].x, &v[i].y);

    for(int i=1;i<n;++i){
        k=0;
        for(int j=i+1;j<=n;++j)
            a[i][++k].p=j, a[i][k].dist=distanta(v[i].x, v[i].y, v[j].x, v[j].y);
    }

    for(int i=1;i<n;++i)
        std::sort(a[i]+1, a[i]+n-i+1, cmp);

    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
        {
            d=distanta(v[i].x, v[i].y, v[j].x, v[j].y);

            st=1;
            dr=n-j;
            f=0;

            while(st<=dr && !f)
            {
                m=(st+dr)/2;
                if(abs1(a[j][m].dist - d) < EPS)
                    f=1, point=a[j][m].p;
                else
                {
                    if(a[j][m].dist < d)
                        st=m+1;
                    else dr=m-1;
                }
            }
            if(f)
                if(abs1(distanta(v[i].x, v[i].y, v[point].x, v[point].y) - d) < EPS)
                    ans++;
        }

    printf("%d", ans);

    return 0;
}