Cod sursa(job #2876408)

Utilizator mateitudordmDumitru Matei mateitudordm Data 23 martie 2022 11:28:29
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda masonii Marime 1.68 kb
#include <fstream>
#include <algorithm>
#define nmax 1000
#define inf 2000000000

using namespace std;

struct pct
{
    int x, y;
};
bool cmp (pct a, pct b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
struct panta
{
    int numa, numi;
    bool operator< (const panta& a)const
    {
        if (numa == a.numa)
            return numi < a.numi;
        return numa < a.numa;
    }
};
pct v[nmax + 1];
panta pante[nmax * nmax + 1];

int main()
{
    ifstream cin ("trapez.in");
    ofstream cout ("trapez.out");
    int n, i, j, act, gcd, p = 0, cnt = 0;
    long long tot = 0;
    panta x;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> v[i].x >> v[i].y;
    sort (v + 1, v + n + 1, cmp);
    for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
        {
            if (v[j].x - v[i].x == 0)
                x = {inf, inf};
            else
            {
                gcd = __gcd (v[j].y - v[i].y, v[j].x - v[i].x);
                if (gcd == 0)
                    gcd = 1;
                x = { (v[j].y - v[i].y) / gcd, (v[j].x - v[i].x) / gcd};
                if (x.numa < 0 && x.numi < 0)
                    x.numa *= -1, x.numi *= -1;
                else if (x.numi < 0)
                    x.numa *= -1, x.numi *= -1;
            }
            pante[++p] = x;
        }
    sort (pante + 1, pante + p + 1);
    for (i = 1; i <= p; i++)
    {
        if (pante[i].numa != pante[i - 1].numa || pante[i].numi != pante[i - 1].numi || i == 1)
            tot += (cnt - 1) * cnt / 2, cnt = 1;
        else
            cnt++;
    }
    tot += (cnt - 1) * cnt / 2;
    cout << tot;
    return 0;
}