Cod sursa(job #1177329)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 26 aprilie 2014 12:16:51
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#define eps 0.001
#include <algorithm>
#include <cmath>
using namespace std;
FILE *f=fopen("trapez.in","r");
FILE *g=fopen("trapez.out","w");
double v[500001];
int nr,tot;
long long sol;
int x[1001],y[1001];

void qs(int p,int q)
{int st=p,dr=q;
double x=v[(st+dr)>>1];

do {while (st<q&&v[st]<x) st++;
    while (dr>p&&v[dr]>x) dr--;
    if (st<=dr) {swap(v[st],v[dr]);
                 st++;dr--;
                 }
    }while (st<=dr);
if (p<dr) qs(p,dr);
if (st<q) qs(st,q);



}



int main()
{int i,j,n;
fscanf(f,"%d",&n);
for (i=1;i<=n;i++) fscanf(f,"%d %d",&x[i],&y[i]);

for (i=1;i<n;i++) for (j=i+1;j<=n;j++) if (x[i]!=x[j])
         if (x[j]!=x[i]) v[++nr]=1.0*(y[j]-y[i])/(x[j]-x[i]);

qs(1,nr);
//sort(v+1,v+nr+1);

i=1;
while (i<=nr) {j=i;
               while (j<nr&&abs(v[i]-v[j+1])<eps) j++;
               tot=j-i+1;
               sol+=(tot*(tot-1))>>1;
               i=j+1;
               }
fprintf(g,"%lld\n",sol);






return 0;
}