Cod sursa(job #2073231)

Utilizator MrRobotMrRobot MrRobot Data 22 noiembrie 2017 20:55:49
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

struct {
    int x, y;
} p[1000], m[1000000];

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

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

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);
    }
}

/*void sortare(int k)
{
    int i, j;
    for(i=0; i<k; i++)
        for(j=i+1; j<=k; j++)
        {
            if( (m[i].x * m[j].y) > (m[i].y * m[j].x) )
            {
                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;
            }
        }
}*/

int main()
{
    int n, i, j;
    long long nr_part=0, nr_total=1, nr_x0=1;
    fin>>n;

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

    int k = -1;
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
        {
            if(p[i].x == p[j].x)
                nr_x0++;
            else
            {
                ++k;
                m[k].x = p[j].y - p[i].y;
                m[k].y = p[j].x - p[i].x;
            }
        }

    //cout<<"nr_x0: "<<nr_x0<<endl;

    /*cout<<"nesortate pantele:"<<endl;
    for(i=0; i<=k; i++)
        cout<<m[i].x<<" "<<m[i].y<<endl;
    cout<<endl;*/

    qsort(0, k);
    //sortare(k);

    /*cout<<"sortate pantele:"<<endl;
    for(i=0; i<=k; i++)
        cout<<m[i].x<<" "<<m[i].y<<endl;
    cout<<endl;*/

    if(nr_x0 > 2)
        nr_x0 *= nr_x0-1;
    else
        nr_x0 = 1;
    nr_total *= nr_x0;
    i=1;
    while( i < n )
    {
        nr_part=0;
        while( p[i].x * p[i-1].y == p[i].y * p[i-1].x )
        {
            nr_part++;
            i++;
        }
        if(nr_part > 2)
        {
            nr_part = nr_part*(nr_part-1);
            nr_total *= nr_part;
        }
        i++;
    }
    fout<<nr_total;
    return 0;
}