Pagini recente » Cod sursa (job #1366658) | Cod sursa (job #2272824) | Cod sursa (job #2105016) | Cod sursa (job #269418) | Cod sursa (job #1388481)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1001
typedef struct
{
long left, right;
long dx, dy; //ezek az egyenes iranytenyezoi
unsigned short nr; //ennyi parhuzamos el van ebbol a fajtabol
} btree;
typedef struct
{
long x, y;
} point;
btree bt[MAXN*MAXN];
unsigned long btnr; //a bt-ben lvo elemek szama
point a[MAXN];
unsigned short n;
unsigned long long o=0; //ennyi trapezt kaptunk
void init_bt(long idx, long dx, long dy)
{
bt[idx].dx=dx;
bt[idx].dy=dy;
bt[idx].nr=1;
bt[idx].left=bt[idx].right=-1; //meg nincs ilyen
}
int comp_line(long dx1, long dy1, long dx2, long dy2)
{
if (dx1==0)
return (dx2==0? 0 : 1);
else
if (dx2==0)
return -1;
else
if (dy1==0)
return (dy2==0? 0 : -1);
else
if (dy2==0)
return 1;
else
{
long long prod1=dx1*dy2, prod2=dx2*dy1;
if (prod1<prod2)
return -1;
else
return (prod1==prod2 ? 0 : 1);
}
}
void add_to_tree(point p1, point p2)
{
long dx=p1.x-p2.x, dy=p1.y-p2.y;
if (btnr==0)
{
init_bt(0, dx, dy);
btnr++;
}
else
{
long idx1, idx2;
int dif=-2;
idx1=idx2=0;
while ((idx1!=-1)&&((dif=comp_line(dx, dy, bt[idx1].dx, bt[idx1].dy))!=0)) //tort osszehasonlitas
{
idx2=idx1;
if (dif==-1)
idx1=bt[idx1].left;
else
idx1=bt[idx1].right;
}
if (idx1==-1) //a masik kondicionak igaznak kell lennie
{
init_bt(btnr, dx, dy);
if (dif==-1)
bt[idx2].left=btnr;
else //uj elem hozzadasa
bt[idx2].right=btnr;
btnr++;
}
else //trapezt kaptunk
{
o+=bt[idx1].nr; //ennyi uj van
bt[idx1].nr++;
}
}
}
int main()
{
FILE * fi, * fo;
unsigned short i, j;
fi=fopen("trapez.in", "rt");
fo=fopen("trapez.out", "wt");
fscanf(fi, "%hu", &n);
btnr=0;
o=0;
for (i=0; i!=n; i++)
{
fscanf(fi, "%ld%ld", &a[i].x, &a[i].y);
for (j=0; j!=i; j++) //facem dreptele
add_to_tree(a[j], a[i]);
}
fprintf(fo, "%llu", o); //es meg is vagyunk
fclose(fi);
fclose(fo);
return 0;
}