Cod sursa(job #2078722)

Utilizator MrRobotMrRobot MrRobot Data 29 noiembrie 2017 21:03:06
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <cmath>
//#include <algorithm>

using namespace std;

pair< long long, long long> p[1000], m[1000000];

///p: A(x, y) <=> A(first, second)
///m: dif de y/ dif de x => m[].first (x) = dif de y (second)
///                         m[].second (y) = dif de x (first)

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

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


int part_Hoare ( int s, int d )
{

    int i, j;
        i = s-1;
        j= d+1;
    int randpoz, r1, r2, r3;
    int nr = d-s+1;

    r1 = rand() % nr + s;
    r2 = rand() % nr + s;
    r3 = rand() % nr + s;

    int minr, maxr;
    minr = min ( min(r1, r2), min(r2, r3) );
    maxr = max ( max(r1, r2), max(r2, r3) );

    randpoz = r1+r2+r3 - minr-maxr;

    int pivot_x = m[randpoz].first;
    int pivot_y = m[randpoz].second;

    while (true){
        do
        {
            ++i;
        }while( m[i].first * pivot_y < m[i].second * pivot_x );
        do
        {
            --j;
        }while( m[j].first * pivot_y > m[j].second * pivot_x);
        if( i>=j )
            return j;
        //swap
        int aux_x, aux_y;
        aux_x = m[i].first;
        aux_y = m[i].second;
        m[i].first = m[j].first;
        m[i].second = m[j].second;
        m[j].first = aux_x;
        m[j].second = aux_y;
    }
}

void qsort (int i, int j)
{
    if(i<j){
        int k = part_Hoare( i, j );
        qsort(i, k);
        qsort(k+1, j);
    }
}



int main()
{

    int n, i;

    fin >> n;

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


    int j, k=-1, m_0 = 0;;

    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
        {
            if( p[i].first == p[j].first )
            {
                m_0++;
            }
            else
            {
                m[++k].first = p[j].second - p[i].second;
                m[k].second = p[j].first - p[i].first;
                //int d = cmmdc( abs(m[k].x), abs(m[k].y) );
                //m[k].x /= d;
                //m[k].y /=d;
            }
        }

    if(m_0 != 0)
    {
        m_0++;
        if(m_0 == 2)
            m_0 = 1;
        else
            m_0 = m_0*(m_0-1)/2;
    }



    //sort( m, m + k+1);
    qsort(0, k);



    int nr_total=m_0, nr_part;

    i=1;
    while ( i <= k )
    {
        nr_part = 1;
        //while( (m[i].first * m[i-1].second == m[i].second * m[i-1].first) && (i<=k) )
        while( m[i] == m[i-1] )
        {
            nr_part++;
            i++;
        }

       if(nr_part > 1)
       {
            if(nr_part > 2)
                nr_part = nr_part*(nr_part-1)/2;
            if(nr_part == 2)
                nr_part = 1;
            nr_total += nr_part;
       }

        i++;
    }
    fout<<nr_total;
    return 0;

}