Cod sursa(job #2693258)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 5 ianuarie 2021 13:13:52
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("trapez.in");
ofstream fout("trapez.out");

pair <int, int> p[1001];
pair <int, int> d[1000001];

int gcd(int a, int b)
{
    int r;
    while (b)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int n, i, j, gcdv, k = 0, ap;
    int rasp = 0;

    fin >> n;
    for (i = 1; i<=n; i++)
        fin >>  p[i].first >> p[i].second;
    sort(p+1, p+n+1);


    for (i = 1; i<=n; i++)
        for (j = i+1; j<=n; j++)
        {
            gcdv = gcd(p[j].first - p[i].first, abs(p[j].second - p[i].second));
            d[++k] = {(p[j].first - p[i].first)/gcdv, (p[j].second - p[i].second)/gcdv};
        }

    sort(d+1, d+k+1);
    ap = 1;
    for (i = 2; i<=k; i++)
    {
        if (d[i] == d[i-1])
            ap++;
        else
        {
            rasp = rasp + ap*(ap-1)/2;
            ap = 1;
        }
    }
    rasp = rasp + ap * (ap-1)/2;

    fout << rasp;
	return 0;
}