Pagini recente » Cod sursa (job #2612329) | Cod sursa (job #2738730) | Cod sursa (job #24847) | Cod sursa (job #2510938) | Cod sursa (job #2078722)
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <cmath>
//#include <algorithm>
using namespace std;
pair< long long, long long> p[1000], m[1000000];
///p: A(x, y) <=> A(first, second)
///m: dif de y/ dif de x => m[].first (x) = dif de y (second)
/// m[].second (y) = dif de x (first)
ifstream fin("trapez.in");
ofstream fout("trapez.out");
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].first;
int pivot_y = m[randpoz].second;
while (true){
do
{
++i;
}while( m[i].first * pivot_y < m[i].second * pivot_x );
do
{
--j;
}while( m[j].first * pivot_y > m[j].second * pivot_x);
if( i>=j )
return j;
//swap
int aux_x, aux_y;
aux_x = m[i].first;
aux_y = m[i].second;
m[i].first = m[j].first;
m[i].second = m[j].second;
m[j].first = aux_x;
m[j].second = 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;
fin >> n;
for(i=0; i<n; i++)
fin >> p[i].first >> p[i].second;
int j, k=-1, m_0 = 0;;
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
{
if( p[i].first == p[j].first )
{
m_0++;
}
else
{
m[++k].first = p[j].second - p[i].second;
m[k].second = p[j].first - p[i].first;
//int d = cmmdc( abs(m[k].x), abs(m[k].y) );
//m[k].x /= d;
//m[k].y /=d;
}
}
if(m_0 != 0)
{
m_0++;
if(m_0 == 2)
m_0 = 1;
else
m_0 = m_0*(m_0-1)/2;
}
//sort( m, m + k+1);
qsort(0, k);
int nr_total=m_0, nr_part;
i=1;
while ( i <= k )
{
nr_part = 1;
//while( (m[i].first * m[i-1].second == m[i].second * m[i-1].first) && (i<=k) )
while( m[i] == m[i-1] )
{
nr_part++;
i++;
}
if(nr_part > 1)
{
if(nr_part > 2)
nr_part = nr_part*(nr_part-1)/2;
if(nr_part == 2)
nr_part = 1;
nr_total += nr_part;
}
i++;
}
fout<<nr_total;
return 0;
}