Cod sursa(job #3185127)

Utilizator paull122Paul Ion paull122 Data 17 decembrie 2023 23:24:08
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

#define ll long long
#define HASH_BASE 17
#define HASH_SIZE 256
using namespace std;
ifstream fin("trapez.in");
ofstream fout("trapez.out");

ll gcd(ll a,ll b)
{
    if(!b || !a)
    {
        return 1;
    }
    while(b)
    {
        ll r=a%b;
        a=b;
        b=r;
    }
    return a;
}
struct p
{
    int x,y;
};
p a[10001];

vector<pair<ll,ll>> v;
ll ox,oy;
int main()
{
    int m;
    fin >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> a[i].x >> a[i].y;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            ll n=a[j].y-a[i].y;
            ll d=a[j].x-a[i].x;
            ll r=gcd(n,d);
            n/=r,d/=r;
            if((n<0 && d<0) || (n>=0 && d<0))
            {
                n=-n;
                d=-d;
            }
            if(d==0)
            {
                oy++;
                continue;
            }
            if(n==0)
            {
                ox++;
                continue;
            }
            v.push_back({n,d});
        }
    }
    ll cnt=0;
    cnt += (ox*(ox-1) + oy*(oy-1) );
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        ll k=1;
        int j=i;
        i++;
        while(i<v.size() && v[j]==v[i])
        {
            ++k;
            ++i;
        }
        i--;
        cnt += k*(k-1);
    }
    fout << cnt/2;
}