Cod sursa(job #1388517)

Utilizator kagy85Kolumban Antal kagy85 Data 15 martie 2015 15:38:30
Problema Trapez Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 2.64 kb
#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;
}