Cod sursa(job #96033)

Utilizator andySeserman Andrei Stefan andy Data 31 octombrie 2007 08:52:53
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#define MAX 1000001
#define eps 0.001
using namespace std;

struct Punct {
    long x;
    long y;
} a[MAX], p[MAX];
int c[MAX];

long n, nrtrap, k, y, nr;

void Read();
void Segm();
void Quick(int st,  int dr);
ofstream fout ("trapez.out");

int main()
{
    nrtrap = 0;
    y = 0;
    Read();
    Segm();
    Quick(1,k);
    for ( int i = 1; i <= k; i++ )
    {
        nr = 1;
        if ( c[i] != 1 )
        {
            if ( ((double)p[i].y/(double)p[i].x) == ((double)p[i+1].y/(double)p[i+1].x) )
            {
                int l = i;
                do
                {
                    l++;
                    nr++;
                } while(((double)p[l].y/(double)p[l].x) == ((double)p[l + 1].y/(double)p[l+1].x));
                i = l;
                nrtrap += ((nr* (nr-1)) / 2); 
            }
        }
        else
        {
            int u = i;
            do
            {
                u++;
                nr++;
            } while ( c[u] == 1 );    
            nr--;
            if ( nr >= 2 )  nrtrap += ((nr* (nr-1)) / 2); 
        }           
                        
             
    } 
    fout << nrtrap; 
    fout.close();
    return 0;
}         

void Read()
{
    ifstream fin ("trapez.in");
    fin >> n;
    for ( int i = 1; i <= n; i++ )
        fin >> a[i].x >> a[i].y;
    fin.close();
}

void Segm()
{
    k = 0;
    for ( int i = 1; i < n; i++ )
    {
        for ( int j = i + 1; j <= n; j++ )
        {
            k++;
            p[k].y = a[j].y - a[i].y;
            c[k] = 0;
            if ( a[j].x - a[i].x  == 0 )
            {
                c[k] = 1;
                p[k].x = 0;
            }    
            else    p[k].x = a[j].x - a[i].x;
        }
    }
}            
                    
void Quick(int st, int dr)
{
    Punct pivot = p[st];
    int i = st - 1; int j = dr + 1;
    do
    {
        do { i++; } while ( ((double)pivot.y/(double)pivot.x) > ((double)p[i].y/(double)p[i].x) );  
        do { j--; } while ( ((double)p[j].y/(double)p[j].x) > ((double)pivot.y/(double)pivot.x) ); 
        if (i <= j)
        {
            Punct aux = p[i];
            p[i] = p[j];
            p[j] = aux;
        }
    } while ( i <= j);
        
    if ( i < dr) Quick(i, dr);
    if ( st < j) Quick(st, j);       
}