Pagini recente » Cod sursa (job #64532) | Cod sursa (job #991162) | Cod sursa (job #1752467) | Cod sursa (job #2554261) | Cod sursa (job #1388517)
#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)
{
dx1*=-1;
dy1*=-1;
}
if (dx2<0)
{
dx2*=-1;
dy2*=-1;
}
if (dy1==0)
{
if (dy2==0)
{
if (dx1*dx2<0) //eleg erdekes a heyzet
return (dx1>0) ? 1 : -1;
else
return 0; //megeggyeznek
}
else
return (dx1>0) ? 1 : -1; //fuggolege egyenes enten ez dont
}
else
if (dy2==0)
return (dx2>0) ? -1 : 1; //e menten a fuggoleges egyenes menten pedig ez dont
else //ferde egyenesek osszehasonlitasa
return (dx1 * dy2 > dy1 *dx2) ? 1 : ((dx1 * dy2 == dy1 *dx2) ? 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
if ((a[i].x!=a[j].x) || (a[i].y!=a[j].y))
add_to_tree(a[j], a[i]);
}
fprintf(fo, "%llu", o); //es meg is vagyunk
fclose(fi);
fclose(fo);
return 0;
}