Cod sursa(job #3185109)

Utilizator paull122Paul Ion paull122 Data 17 decembrie 2023 23:08:53
Problema Trapez Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 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");

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

map<pair<int,int>,ll> M;
ll ox,oy;
int main()
{
    int n;
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i].x >> a[i].y;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int n=a[j].y-a[i].y;
            int d=a[j].x-a[i].x;
            int r=gcd(n,d);
            n/=r,d/=r;
            if(n<0)
            {
                if(d<0)
                {
                    n=-n;
                    d=-d;
                }
            }
            else if(d<0)
            {
                d=-d;
                n=-n;
            }
            if(d==0)
            {
                oy++;
                continue;
            }
            if(n==0)
            {
                ox++;
                continue;
            }
            M[{n,d}]++;
        }
    }
    ll cnt=0;
    for(auto i : M)
    {
        cnt += (i.second * i.second-1);
    }
    cnt += (ox*(ox-1) + oy*(oy-1) );
    cnt/=2;
    fout << cnt;
}