Cod sursa(job #1083015)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 15 ianuarie 2014 15:07:36
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <cstdio>
#include <algorithm>
#define rad3 1.73205081
FILE *f,*g;

using namespace std;

typedef struct punct{
    double x;
    double y;
}pct;

pct p[1500];
double eps=10e-4;

int cmp(pct a, pct b)
{
    if(a.x-b.x < eps && a.x-b.x > -eps)
    {
        if(a.y-b.y < eps && a.y-b.y > -eps)
            return 0;
        else
            if(a.y-b.y > eps)
                return 1;
        else return -1;
    }
    if(a.x-b.x > eps)
        return 1;
    return -1;
}
void quicksort(int left, int right)
{
    int i=left, j=right;
    double tmpo;
    pct tmp, piv;
    piv = p[(left + right) / 2];
    while(i<=j)
    {
        while(p[i].x < piv.x)
            i++;
        while(p[j].x > piv.x)
            j--;
        if(i<=j)
        {
            tmp = p[i];
            p[i] = p[j];
            p[j] = tmp;
            if(p[i].x == p[j].x)
            {
                if(p[i].y > p[j].y)
                {
                    tmpo=p[i].y;
                    p[i].y=p[j].y;
                    p[j].y=tmpo;
                }
            }
            i++;
            j--;
        }

    }
    if(left<j)
        quicksort(left,j);
    if(i<right)
        quicksort(i,right);
}

int caut(pct r, int left, int right)
{
    int m;
    if(left<=right)
    {
        m=(left+right)/2;
        if(cmp(p[m],r)==0)
            return 1;
        else
            if(cmp(p[m],r)<0)
                return caut(r,m+1,right);
            else
                return caut(r,left,m-1);
    }
    else return 0;
}

int main()
{
    int n,i,j;
    double x1, y1;
    f=fopen("triang.in","r");
    g=fopen("triang.out","w");
    fscanf(f,"%d",&n);
    pct aux;
    for(i=0;i<n;i++)
        fscanf(f,"%lf %lf",&p[i].x,&p[i].y);
    quicksort(0,n-1);
    int nr=0;
    for(i=0 ; i<n-1 ; i++)
    {
        for(j=i+1 ; j<n ; j++)
        {
            x1 = p[i].x + p[i].y * rad3 + p[j].x - p[j].y * rad3;
            y1 = -p[i].x * rad3 + p[i].y + p[j].y + p[j].x * rad3;
            aux.x = x1 / 2.0;
            aux.y = y1 / 2.0;
            if(caut(aux,0,n-1) == 1)
                nr++;
            x1 = p[i].x + p[j].x + (p[j].y - p[i].y) * rad3;
            y1 = p[i].x * rad3 + p[j].y + p[i].y - p[j].x * rad3;
            aux.x = x1 / 2.0;
            aux.y = y1 / 2.0;
            if(caut(aux,0,n-1) == 1)
                nr++;
        }
    }
    fprintf(g,"%d",nr/3);
    fclose(f);
    fclose(g);
    return 0;
}