Cod sursa(job #2922226)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 6 septembrie 2022 17:19:49
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>

typedef long long int ll;
const int NMAX=1505;

double abs(double x) {return x<0?-x:x;}

struct pt
{
    double x, y;

    bool operator==(pt b)
    {
        return abs(this->x-b.x)<=0.001 && abs(this->y-b.y)<=0.001;
    }

    bool operator<(pt b)
    {
        return this->x<b.x;
    }
} v[NMAX];

int N;
const double RAD=0.86602540378443864676372317075294;

int main()
{
    FILE* f=fopen("triang.in", "r"), *g=fopen("triang.out", "w");
    int i, j, l, r, mid, answer=0;
    pt aux, delta;
    fscanf(f, "%d", &N);
    for(i=0;i<N;++i)
        fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
    fclose(f);

    std::sort(v, v+N);
    for(i=0;i<N;++i)
    {
        for(j=i+1;j<N;++j)
        {
            delta.x=v[j].x-v[i].x;
            delta.y=v[j].y-v[i].y;
            aux.x=v[i].x+0.5*delta.x+RAD*delta.y;
            aux.y=v[i].y+0.5*delta.y-RAD*delta.x;

            //search for aux
            l=j;
            r=N;
            while(r-l>1)
            {
                mid=(l+r)>>1;
                if(v[mid]==aux)
                    ++answer, l=-2, r=-2;
                else if(v[mid].x<=aux.x)
                    l=mid;
                else
                    r=mid;
            }
            if(l!=j && v[l]==aux)
            {
                //found
                ++answer;
            }
        }
    }

    fprintf(g, "%d", answer);

    fclose(g);
    return 0;
}