Pagini recente » Cod sursa (job #1223941) | Cod sursa (job #2107941) | Cod sursa (job #1967591) | Cod sursa (job #1592691) | Cod sursa (job #2079181)
#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;
}