Cod sursa(job #1206336)

Utilizator Darius15Darius Pop Darius15 Data 9 iulie 2014 17:26:28
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
struct poz{int nr;double val;};
poz b[2000];
double x[2002],y[2002],dist[2000][2000];
ifstream f("triang.in");
ofstream g("triang.out");
bool cmp(poz a,poz b)
{
    if (a.val==b.val)
    return a.nr<b.nr;
    return a.val<b.val;
}
int n,i,j,o,st,dr,m;
long long sol;
int main()
{
     f>>n;
     for (i=1;i<=n;i++)
     f>>x[i]>>y[i];
    for (i=1;i<=n;i++)
         for (j=1;j<=n;j++)
         dist[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    for (i=1;i<=n-2;i++)
    {
        o=0;
        for (j=1;j<=n;j++)
        if (i!=j) b[++o].val=dist[i][j],b[o].nr=j;
        sort(b+1,b+n,cmp);
        for (j=i+2;j<=n;j++)
        {
            st=i,dr=j;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if (-0.001<dist[i][j]-b[m].val && dist[i][j]-b[m].val<0.001) st=dr+1;
                else if (dist[i][j]>b[m].val) dr=m-1;
                else st=m+1;
            }
            while(-0.001<dist[i][j]-b[m].val && dist[i][j]-b[m].val<0.001)
            {
                if (-0.001<dist[i][j]-b[m].val && dist[i][j]-b[m].val<0.001 && i<b[m].nr && b[m].nr<j) sol++;
                m++;
            }
        }
    }
    g<<sol;
        return 0;
}