Cod sursa(job #1356267)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 23 februarie 2015 12:23:34
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
#define DMAX 1020
#define x first
#define y second
#define pi pair<long long, long long>
using namespace std;

long long n, ans,a, b;

struct point
{
    long long x, y;

    bool operator()(const point &a, const point &b)
    {
        return a.x*b.y<a.y*b.x;
    }


}pl[DMAX];
long long nx, ny;
map<pi, long long> m;

vector <point> v;

int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);

    //freopen("in.txt", "r", stdin);

    scanf("%i", &n);

    for(long long i=1;i<=n;i++)
    {
        scanf("%i %i", &a, &b);
        point p;
        p.x=a;
        p.y=b;
        pl[i]=p;
    }

    for(long long i=1;i<n;i++)
    for(long long j=i+1;j<=n;j++)
    {
        long long X=abs(pl[i].x-pl[j].x);
        long long Y=abs(pl[i].y-pl[j].y);
        if(X==0)
            nx++;
        else if(Y==0)
            ny++;
        else{
        long long g=__gcd(X, Y);
        X/=g;
        Y/=g;

        point l;
        l.x=X;
        l.y=Y;

        v.push_back(l);
        }

    }

    sort(v.begin(), v.end(), point());
    long long k=1;
    for(long long i=1;i<v.size();i++)
    {
        if(v[i].x==v[i-1].x && v[i].y==v[i-1].y)
            k++;
        else{
        ans+=(k*(k-1)/2);
        k=1;
        }
    }
    ans+=(k*(k-1)/2);
    k=nx;
    ans+=(k*(k-1)/2);
    k=ny;
    ans+=(k*(k-1)/2);

    cout<<ans<<'\n';
    return 0;
}