Pagini recente » Cod sursa (job #145135) | Cod sursa (job #3213059) | Cod sursa (job #2056022) | Cod sursa (job #3286635) | Cod sursa (job #21565)
Cod sursa(job #21565)
#include <cstdio>
#define dim 1 << 10
int N, M, K, ret;
int x[dim], y[dim], px[dim*dim], py[dim*dim];
int euclid( int, int );
void heapup( int );
void restore( int, int );
void swap( int, int );
int main()
{
freopen("trapez.in", "r", stdin);
freopen("trapez.out", "w", stdout);
scanf("%d", &N);
int i, j, a, b, c;
for(i=1; i<=N; ++i)
scanf("%d %d", x+i, y+i);
for(i=1; i<=N; ++i)
for(j=i+1; j<=N; ++j)
{
++ M;
px[M] = x[j] - x[i];
py[M] = y[j] - y[i];
c = euclid( px[M], py[M] );
while( c != 1 )
{
px[M] /= c;
py[M] /= c;
c = euclid( px[M], py[M] );
}
}
for(i=2; i<=M; ++i)
heapup(i);
for(i=M; i>1;)
{
swap(1, i);
-- i;
restore(1, i);
}
a = px[1]; b = py[1]; K = 1;
for(i=2; i<=M; ++i)
if( px[i] == a && py[i] == b )
{
++ K;
K -= K >= 666013 ? 666013 : 0;
}
else
{
ret += (K * (K-1)) >> 1;
ret -= ret >= 666013 ? 666013 : 0;
K = 1;
a = px[i];
b = py[i];
}
printf("%d", ret);
fclose(stdin); fclose(stdout);
return 0;
}
int euclid( int x, int y )
{
int r;
while( y )
{
r = x % y;
x = y;
y = r;
}
return x;
}
void heapup( int k )
{
if( k <= 1 )
return;
int t = k >> 1;
if( px[t] < px[k] || px[t] == px[k] && py[t] < py[k] )
{
swap(t, k);
heapup(t);
}
}
void swap( int i, int j )
{
px[i] ^= px[j] ^= px[i] ^= px[j];
py[i] ^= py[j] ^= py[i] ^= py[j];
}
void restore( int r, int b )
{
if( r << 1 <= b )
{
int stx, drx, sty, dry, x;
stx = px[r << 1];
sty = py[r << 1];
if( (r << 1)+1 <= b )
{
drx = px[(r << 1)+1];
dry = py[(r << 1)+1];
}
else
{
drx = stx-1;
dry = sty-1;
}
if( stx > drx || stx == drx && sty > dry )
x = r << 1;
else
x = (r << 1)+1;
if( px[r] < px[x] || px[r] == px[x] && py[r] < py[x] )
{
swap(r, x);
restore(x, b);
}
}
}