Pagini recente » Cod sursa (job #1356849) | Cod sursa (job #376100) | Cod sursa (job #1451070) | Cod sursa (job #2099390) | Cod sursa (job #157588)
Cod sursa(job #157588)
#include <stdio.h>
#define in "trapez.in"
#define out "trapez.out"
#define eps 1e-14
#include <math.h>
struct Punct{
int x, y;
}a[1000000], l[1000000];
int m=0;
int i, n, j, k, t, r, u;
int rest, cmmd, select[1000000];
double sir[1000000];
int sol = 0;
FILE *fout = fopen(out,"w");
void Read();
void Panta();
void Quick(int st, int dr);
void Write();
int Numar(int n);
int Facto(int k);
int Cmmdc(int a, int b);
void Solve();
int main()
{
Read();
Panta();
Quick(1,m);
Solve();
return 0;
}
void Read()
{
int unu, doi;
FILE *fin = fopen(in,"r");
fscanf(fin,"%d",&n);
for (int i = 1; i <= n; i++ )
{
fscanf(fin,"%d%d", &unu, &doi);
a[i].x = unu;
a[i].y = doi;
}
fclose(fin);
}
void Panta()
{
r = 0;
sol = 0;
for (int i = 1; i < n; i++ )
{
for (int j = i+1; j <= n; j++ )
{
int t,u;
t = a[j].y - a[i].y;
u = a[j].x - a[i].x;
if ( u == 0 )
{
r++;
}
else
{
++m;
sir[m] = (double)t/u;
}
}
}
//sol += r*(r-1)/2;
}
void Quick(int st, int dr)
{
int i = st-1, j = dr+1;
double pivot = sir[st], aux;
do
{
do { i++; } while ( pivot - sir[i] > eps );
do { j--; } while ( sir[j] - pivot > eps );
if ( i <= j )
{
aux = sir[i];
sir[i] = sir[j];
sir[j] = aux;
}
}
while ( i <= j );
if ( st < j ) Quick(st, j);
if ( i < dr ) Quick(i, dr);
}
void Solve()
{
int r , k, i = 1;
while ( i < m )
{
r = 1;
k = 1;
if ( fabs(sir[i]-sir[i+1]) < eps )
{
int j = i+1;
while ( fabs(sir[i]-sir[j]) < eps )
{
r++;
j++;
}
k = j - i;
}
i += k;
sol += r*(r-1)/2;
}
/* for ( int i = 1; i <= m; i++ )
fprintf(fout,"%f ", sir[i]); */
fprintf(fout,"%d",sol);
fclose(fout);
}
int Cmmdc(int a, int b)
{
if ( b == 0 ) return a;
return Cmmdc(b, a%b);
}