Cod sursa(job #2837241)

Utilizator AswVwsACamburu Luca AswVwsA Data 21 ianuarie 2022 22:45:54
Problema Trapez Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
//#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#define ll long long
using namespace std;
struct panta
{
    int sus, jos;
};

struct pct
{
    int x, y;
};

bool neg(panta a)
{
    if (a.sus < 0)
    {
        if (a.jos < 0) return 0;
        return 1;
    }
    if (a.jos >= 0)
        return 0;
    return 1;
}
bool cmp(panta a, panta b)
{
    bool sgn1 = neg(a), sgn2 = neg(b);
    if (sgn1 and sgn2)
        return abs(1LL * a.sus * b.jos) > abs(1LL * a.jos * b.sus);
    if (!sgn1 and !sgn2)
        return 1LL * a.sus * b.jos < 1LL * a.jos * b.sus;
    return sgn1;
}

bool egal(panta a, panta b)
{
    return 1LL * a.sus * b.jos == 1LL * a.jos * b.sus;
}
vector <panta> v;

const int NMAX = 1003;
pct a[NMAX];
int main()
{
    ifstream cin("trapez.in");
    ofstream cout("trapez.out");
    /*
    panta x, y;
    x.sus = 1;
    x.jos = -2;
    y.sus = 4;
    y.jos = -1;
    cout << cmp(x, y);
    return 0;*/
    int n, i, j, weird = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    for (i = 1; i + 1 <= n; i++)
        for (j = i + 1; j <= n; j++)
        {
            panta aux;
            aux.sus = a[j].y - a[i].y;
            aux.jos = a[j].x - a[i].x;
            if (aux.jos == 0)
                weird++;
            else
            v.push_back(aux);
        }
    sort(v.begin(), v.end(), cmp);
    /*for (i = 0; i < v.size(); i++)
        cout << v[i].sus << " " << v[i].jos << "\n";
    return 0;*/
    int first = 0, cnt = 1;
    long long ans = 1LL * weird * (weird - 1) / 2;
    for (i = 1; i < v.size(); i++)
        if (egal(v[first], v[i]))
            cnt++;
        else
        {
            ans += 1LL * cnt * (cnt - 1) / 2;
            first = i;
            cnt = 1;
        }
    ans += cnt * (cnt - 1) / 2;
    cout << ans;
}