Cod sursa(job #2455725)

Utilizator cristina-criCristina cristina-cri Data 12 septembrie 2019 16:35:33
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n;

pair<int, int> p[1005];

pair<int, int>m;

vector<pair<int, int>> fr;

int cmmdc(int x, int y)
{
    x=abs(x);
    y=abs(y);
    while(y)
    {
        int r=x%y;
        x=y;
        y=r;
    }
    return x;
}

int combin(int n)
{
    return n*(n-1)/2;
}

int cmp(pair<int, int> a, pair<int, int>b)
{
    return a.first*b.second < a.second*b.first;
}

int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);

    scanf("%d", &n);

    for(int i=1; i<=n; i++)
    {
        scanf("%d %d", &p[i].first, &p[i].second);
    }

    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            m.first=p[j].second-p[i].second;
            m.second=p[j].first-p[i].first;
            int divCom=abs(cmmdc(m.first, m.second));
            if(m.first<0 && m.second<0)
            {
                m.first*=(-1);
                m.second*=(-1);
            }
            else
            {
                if(m.second<0)
                {
                    m.second*=(-1);
                    m.first*=(-1);
                }
            }
            m.first/=divCom;
            m.second/=divCom;
           // printf("%d %d\n", m.first, m.second);
            fr.push_back({m.first, m.second});
        }
    }
    sort(fr.begin(), fr.end(), cmp);
    int sum=0, nr=0;
    for(int i=0; i<fr.size(); i++)
    {
        if(i && fr[i].first == fr[i-1].first && fr[i].second == fr[i-1].second)
            nr++;
        else{
            sum+=combin(nr);
            nr=1;
        }

    }
    printf("%d", sum);
    return 0;
}