Cod sursa(job #1026973)

Utilizator stanescu.raduRadu Stanescu stanescu.radu Data 12 noiembrie 2013 12:33:03
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<fstream>
 
using namespace std;
 
ifstream f ("trapez.in");
ofstream g("trapez.out");
int n,i,x[1005],y[1005],j,nr,k,s;
double p[1000005];
 
void merge (int st, int m, int dr)
{
    int i=st, j=m+1;
    float aux[100000];
    int k=0;
    while (i<=m && j<=dr)
    {
        if (p[i]<=p[j])
        {
            aux[++k]=p[i];
            i++;
        }
        else
        {
            aux[++k]=p[j];
            j++;
        }
        while (i<=m) aux[++k]=p[i++];
        while (j<=dr) aux[++k]=p[j++];
        k=0;
        for (i=st;i<=dr;i++) p[i]=aux[++k];
    }
}
 
void mergesort(int st, int dr)
{
    int m;
    if ((dr-st)<1) return;
    else
    {
        m=(st+dr)/2;
        mergesort(st,m);
        mergesort(m+1,dr);
        merge(st,m,dr);
    }
}
 
int main  ()
{
    f>>n;
    for (i=1;i<=n;i++)
        f>>x[i]>>y[i];
    k=1;
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
        {
            if (x[i]==x[j]) p[k]=9999999;
            else p[k]=((double)(y[j]-y[i]))/(x[j]-x[i]);
            k++;
        }
    mergesort(1,k);
    s=0;
    nr=1;
    for (i=2;i<k;i++)
    {
        if (p[i]==p[i-1]) nr++;
        else
        {
            s+=nr*(nr-1)/2;
            nr=1;
        }
    }
    s+=nr*(nr-1)/2;
    g<<s;
    f.close();
    g.close();
    return 0;
}