Cod sursa(job #1388481)

Utilizator kagy85Kolumban Antal kagy85 Data 15 martie 2015 15:02:28
Problema Trapez Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.43 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)
        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;
}