Cod sursa(job #2014241)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 23 august 2017 11:50:14
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define NMAX 1000
using namespace std;
struct pant
{
    int x,y;
}v[NMAX*NMAX+1];
struct pt
{
    int absc,ord;
}p[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;
}
bool compp(pt a,pt b)
{
    return a.absc<b.absc;
}
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",&p[i].absc,&p[i].ord);
    sort(p+1,p+1+n,compp);
    m=0;
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
            if(p[i].absc!=p[j].absc)
            {
                m++;
                v[m].x=p[j].absc-p[i].absc;
                v[m].y=p[j].ord-p[i].ord;
            }
            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;
    }
    if(drept==0) drept++;
    printf("%lld\n",nr+drept*(drept-1)/2);

    return 0;
}