Cod sursa(job #1592515)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 7 februarie 2016 18:23:57
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <math.h>
#include <algorithm>

#define st first
#define nd second

using namespace std;

const int Mn = 1e3 + 4;
const int oo = 1 << 31;

int gcd(int a,int b)
{
    if (b == 0)
       return a;

    return gcd(b,a % b);
}

long long n,ans;
pair< int,int > ar[Mn],sl[Mn * Mn];

int main()
{
    ifstream fi("trapez.in");
    ofstream fo("trapez.out");

    fi >> n;

    for (int i = 1;i <= n;i++)
        fi >> ar[i].st >> ar[i].nd;

    int it = 1,cnt = 1;
    for (int i = 1;i < n;i++)
        for (int j = i + 1;j <= n;it++,j++)
        {
            int a = ar[i].st - ar[j].st,b = ar[i].nd - ar[j].nd,c = gcd(abs(a),abs(b));
            sl[it] = make_pair(b / c,a / c);
            //printf("%d %d\n",a,b);
        }

    sort(sl + 1,sl + 1 + it);
    for (int i = 2;i <= it;i++)
        if (sl[i] == sl[i - 1])
           cnt++;
      else
        {
           ans += (long long)(cnt * (cnt - 1)) / 2;
           cnt = 1;
        }

    fo << ans << endl;
    return 0;
}