Cod sursa(job #47189)

Utilizator deltaDumitrache Mircea delta Data 3 aprilie 2007 13:50:09
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
using namespace std;
#define MAX 1001
#define eps 0.001

struct Punct {
    int x, y;
} p[MAX];
int n;
struct Dreapta {
    Punct a, b;
    int p1;
    int p2;
    int nrod1, nrod2;
} d[MAX*MAX];
int nrd;
int nrcomb;

void Read();
void Panta();
void Qsort(int st, int dr);
void Solve();
void Write();

ofstream fout("trapez.out");

int main()
{
    Read();
    Panta();
    Qsort(1, nrd);
    Solve();
    Write();
    fout.close();
    return 0;
}

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

void Panta()
{
    int i, j;
    for (i = 1; i < n; i++)
        for (j = i+1; j <= n; j++)
        {
                d[++nrd].a = p[i];
                d[nrd].b = p[j];
                d[nrd].p1 = abs(p[j].y - p[i].y); 
                d[nrd].p2 = abs(p[j].x - p[i].x);
                d[nrd].nrod1 = i;
                d[nrd].nrod2 = j;
        }
    d[nrd+1].p1 = 1, d[nrd+1].p2 = 12356;
}

void Qsort(int st, int dr)
{

	int pv1 = d[st].p1;
	int pv2 = d[st].p2;
	int i = st - 1, j = dr + 1;
	do
  	{
		do { i++; } while ( pv1*d[i].p2 - pv2*d[i].p1 > eps ) ;
		do { j--; } while ( d[j].p1*pv2 - pv1*d[j].p2 > eps );
		if ( i <= j )
		{
			Dreapta aux = d[i];
			d[i] = d[j];
			d[j] = aux;
		}
	} while ( i <= j );

	if ( st < j ) Qsort(st, j);
	if ( i < dr ) Qsort(i, dr);

}

void Solve()
{
    int k = 1;
    int i = 1;
    int aux = 0;
    for (int i = 1; i < nrd; i++)
    {
        aux = i;
        while ( abs (d[i].p1*d[++aux].p2 - d[i].p2*d[aux].p1) < eps) k++;
        nrcomb += k*(k-1) / 2;
     /*   fout << k << " " << nrcomb << " " << d[i-k].p1 << " " 
               << d[i-k].p2 << "\n"; */
        i = aux - 1;
        k = 1;
    }       
   // fout << "\n";
}

void Write()
{
   /* for (int i = 1; i <= nrd; i++)
        fout << d[i].p1 << " " << d[i].p2 << "  " << d[i].nrod1 << " " 
             << d[i].nrod2 <<"\n";  */
    fout << nrcomb << "\n";
}