Cod sursa(job #2079181)

Utilizator nic_irinaChitu Irina nic_irina Data 30 noiembrie 2017 18:31:07
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

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

struct {
    int x, y;
} p[1010], m[1000010];

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].x;
    int pivot_y = m[randpoz].y;

    while (true){
        do
        {
            ++i;
        }while( m[i].x * pivot_y < m[i].y * pivot_x );
        do
        {
            --j;
        }while( m[j].x * pivot_y > m[j].y * pivot_x);
        if( i>=j )
            return j;
        //swap
        int aux_x, aux_y;
        aux_x = m[i].x;
        aux_y = m[i].y;
        m[i].x = m[j].x;
        m[i].y = m[j].y;
        m[j].x = aux_x;
        m[j].y = 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 , j;

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

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

    qsort(1, k);

    int nr_part=0, nr_total=0;

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

        }
    }

    fout << nr_total;
    return 0;
}