Cod sursa(job #2013858)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 22 august 2017 15:27:57
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define NMAX 1000
using namespace std;
struct pant
{
    int x,y;
}v[NMAX*NMAX+1];
int absc[1001],ord[1001];
long long drept;
bool comp(pant a,pant b)
{
    return (long long)a.y*b.x<(long long)a.x*b.y;
}
int cmp(int i,int j)
{
    if((long long)v[i].y*v[j].x==(long long)v[i].x*v[j].y) return 1;
    return 0;
}
int main()
{
    int n,i,m,j;
    long long nr;
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d%d",&absc[i],&ord[i]);
    m=0;
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
            if(absc[i]!=absc[j])
            {
                m++;
                v[m].x=abs(absc[i]-absc[j]);
                v[m].y=ord[i]-ord[j];
            }
            else
                drept++;
    sort(v+1,v+1+m,comp);
    nr=0;
    for(i=1; i<=m;)
    {
        j=i+1;
        while(j<=m && cmp(i,j))
            j++;
        nr+=(long long)(j-i)*(j-i-1)/2;
        i=j;
    }
    printf("%lld\n",nr+drept*(drept-1)/2);

    return 0;
}