Pagini recente » Cod sursa (job #1216326) | Cod sursa (job #1151020) | Cod sursa (job #1620932) | Cod sursa (job #1463117) | Cod sursa (job #255170)
Cod sursa(job #255170)
#include <fstream>
#include <cmath>
using namespace std;
#define dim 500001
#define input "trapez.in"
#define output "trapez.out"
ifstream fin (input);
ofstream fout(output);
struct punct
{
long x, y;
} ;
long n, i, j, m, k, nr_trapez;
punct puncte[1001], aux;
punct pante[dim];
void quick(long li, long ls);
void poz (long li, long ls, long&k );
int main()
{
fin >> n;
for ( i = 1; i <= n; i ++ )
fin >> puncte[i].x >> puncte[i].y;
// calculam pantele
for ( i = 1; i < n; i ++ )
for ( j = i + 1; j <= n; j ++ )
{
m ++;
pante[m].x = (puncte[j].x-puncte[i].x);
pante[m].y = (puncte[j].y-puncte[i].y);
}
quick(1,m);
i = 1;
while ( i <= m - 1)
{
j = i + 1;
while ( (j <= m) && (pante[i].y*pante[j].x == pante[j].y*pante[i].x) )
j ++;
long v = j - i;
// fout << v << " ";
if ( v > 1 )
nr_trapez += ((v)*(v-1) / 2);
i = j;
}
fout << nr_trapez;
return 0;
}
void quick(long li, long ls)
{
if ( li < ls )
{
poz(li, ls, k);
quick(li, k-1);
quick(k+1, ls);
}
}
void poz (long li, long ls, long&k)
{
int i = li, j = ls, i1 = 0, j1 = -1, c;
while ( i < j )
{
if ( pante[i].y*pante[j].x > pante[j].y*pante[i].x )
{
aux = pante[j]; pante[j] = pante[i]; pante[i] = aux;
c = i1;
i1 = -j1; j1 = -c;
}
i += i1;
j += j1;
}
k = i;
}