Pagini recente » Cod sursa (job #1957239) | Cod sursa (job #942166) | Cod sursa (job #1140834) | Cod sursa (job #2350852) | Cod sursa (job #2844010)
#include <stdio.h>
#include <algorithm>
#define N 1000
#define LMAX 20
#define AINF 2000000001
#define EPSILON 0.0001
struct pct {
int x;
int y;
};
float a[(N - 1) * N / 2 + 1];
pct v[N];
int n;
inline bool isEqual( float a, float b ) {
float x = a - b;
if ( x < 0 )
x = -x;
return (x < EPSILON);
}
int firstVal( float v[], int n, float val ) {
int poz = 0, pas = 1 << LMAX;
while ( pas ) {
if ( poz + pas < n && v[poz + pas] < val )
poz += pas;
pas /= 2;
}
if ( poz == 0 && isEqual( v[poz], val ) )
return poz;
if ( isEqual( v[poz + 1], val ) )
return poz + 1;
// nu exista val in vector
return -1;
}
int lastVal( float v[], int n, float val ) {
int poz = 0, pas = 1 << LMAX;
while ( pas ) {
if ( poz + pas < n && v[poz + pas] <= val )
poz += pas;
pas /= 2;
}
if ( isEqual( v[poz], val ) )
return poz;
// nu exista val in vector
return -1;
}
inline float getPanta( pct a, pct b ) {
if ( a.x == b.x )
return AINF;
return (float)(b.y - a.y) / (b.x - a.x);
}
void precalcPanta() {
int poz = 0;
for ( int i = 0; i < n; i ++ )
for ( int j = i + 1; j < n; j ++ )
a[poz ++] = getPanta( v[i], v[j] );
std::sort( a, a + poz );
a[poz] = AINF + 5;
}
bool cmp( const pct& a, const pct& b ) {
if ( a.x < b.x || (a.x == b.x && a.y < b.y) )
return true;
return false;
}
int main() {
FILE *fin, *fout;
int cnt;
float p;
fin = fopen( "trapez.in", "r" );
fscanf( fin, "%d", &n );
for ( int i = 0; i < n; i ++ )
fscanf( fin, "%d%d", &v[i].x, &v[i].y );
fclose( fin );
//std::sort( v, v + n, cmp );
precalcPanta();
cnt = 0;
for ( int i = 0; i < n; i ++ ) {
for ( int j = i + 1; j < n; j ++ ) {
p = getPanta( v[i], v[j] );
cnt += lastVal( a, (n - 1) * n / 2, p ) -
firstVal( a, (n - 1) * n / 2, p );
}
}
fout = fopen( "trapez.out", "w" );
fprintf( fout, "%d\n", cnt / 2 );
fclose( fout );
return 0;
}