Cod sursa(job #2078769)

Utilizator MrRobotMrRobot MrRobot Data 29 noiembrie 2017 22:15:17
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

ifstream fin("trapez.in");
ofstream fout("trapez.out");

pair < int, int > p[1010], m[100010];

int cmmdc(int a, int b)
{
    if( b != 0 )
        return cmmdc(b, a%b);
    else
        return a;
}

int main()
{
    int n, i , j;

    fin >> n;
    int k = 0;
    for(i = 1; i <= n; i++)
    {
        fin >> p[i].first >> p[i].second;

        for(j = 1; j < i; j++)
        {
            if(p[i].first == p[j].first)
            {
                k++;
                m[k].first = m[k].second = 0;
            }
            else
            {
                ++k;
                m[k].first = p[j].second - p[i].second;
                m[k].second = p[j].first - p[i].first;
                int d = cmmdc( abs(m[k].first), abs(m[k].second) );
                m[k].first /= d;
                m[k].second /=d;
                if( (m[k].first < 0) && (m[k].second < 0)  || ( (m[k].first < 0) && (m[k].second > 0) ))
                {
                    m[k].first *= -1;
                    m[k].second *= -1;
                }
            }
        }
    }

    sort(m + 1, m + k + 1);

    int nr_part=0, nr_total=0;

    for(i = 1; i <= k; i++)
    {
        if(m[i] == m[i - 1])
            nr_part++;
        else
        {
            nr_total += nr_part * (nr_part - 1) / 2;
            nr_part = 1;
        }
    }

    fout << nr_total;
    return 0;
}