Cod sursa(job #1326647)

Utilizator acomAndrei Comaneci acom Data 25 ianuarie 2015 19:41:46
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream>
#include<algorithm>
using namespace std;
#define INF 2000000005.0
#define NMAX 500005
#define EPS 0.000001
ifstream fin("trapez.in");
ofstream fout("trapez.out");
int n,m,k,x[1005],y[1005];
double a[NMAX];
long long sol;
int main()
{
    int i,j;
    fin>>n;
    for (i=1;i<=n;++i)
        fin>>x[i]>>y[i];
    for (i=1;i<n;++i)
        for (j=i+1;j<=n;++j)
            if (x[i]==x[j])
                a[++m]=INF;
            else
                a[++m]=(double)(y[j]-y[i])/(x[j]-x[i]);
    sort(a+1,a+m+1);
    for (i=2,k=1;i<=m;++i)
        if (-EPS<a[i]-a[i-1] && a[i]-a[i-1]<EPS)
            ++k;
        else
        {
            if (k>1)
                sol+=1LL*k*(k-1)/2;
            k=1;
        }
    fout<<sol<<"\n";
    return 0;
}