Cod sursa(job #797342)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 13 octombrie 2012 20:58:53
Problema Patrate 3 Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include<stdio.h>
#include<math.h>
#include<fstream>
#include<algorithm>

using namespace std;

#define MAXN 10002
#define EPS 0.000001

typedef struct
{
    double X, Y;
} point;

point v[ MAXN ];
int n, i, j, res;
double X1, X2, X3, X4, Y1, Y2, Y3, Y4, l;

inline double dist(int i, int j)
{
    double res;

    res = sqrt( (v[i].X - v[j].X) * (v[i].X - v[j].X) + (v[i].Y - v[j].Y) * (v[i].Y - v[j].Y) );

    return res;
}

inline int cmp(point i, point j)
{
    if(i.X - j.X > EPS)
        return 0;
    else if(i.X - j.X < -EPS)
        return 1;
        else if(i.Y - j.Y > EPS)
            return 0;
            else return 1;
}

inline double calculate_Y3(double l, double X3)
{
    double a, b, res;

    a = (X2 - X3) * (X2 - X3);
    l *= l;
    b = l - a;
    b = sqrt(b);

    res = fabs(b - Y2);

    return res;
}

inline double calculate_Y4(double l, double X4)
{
    double a, b, res;

    a = (X1 - X4) * (X1 - X4);
    l *= l;
    b = l - a;
    b = sqrt(b);

    res = fabs(b - Y1);

    return res;
}

inline int search_value(double X1, double Y1)
{
    int st, end, mid, i;
    st = 1, end = n;

    while(st <= end)
    {
        mid = (st + end) / 2;
        if( fabs(X1 - v[mid].X) < EPS )
            st = end + 1;
        else
            if( X1 < v[mid].X )
                end = mid - 1;
                else st = mid + 1;
    }

    if( fabs(v[mid].X - X1) < EPS )
    {
        st = mid;
        while( fabs(v[st].X - X1) < EPS && st)
            --st;
        end = mid;
        while( fabs(v[end].X - X1) < EPS && end <= n)
            ++end;

        for(i = st + 1; i < end; ++i)
                if( fabs(v[i].Y - Y1) < EPS)
                    return 1;
    }

    return 0;
}

int main()
{
    ifstream f("patrate3.in");

    f >> n;

    for(i = 1; i <= n; ++i)
        f >> v[i].X >> v[i].Y;

    f.close();

    sort(v+1, v+n+1, cmp);

    for(i = 1; i < n; ++i)
            for(j = i + 1; j <= n; ++j)
            {
                X1 = v[i].X, Y1 = v[i].Y;
                X2 = v[j].X, Y2 = v[j].Y;

                l = dist(i, j);

                X3 = Y2 - Y1 + X2;
                Y3 = calculate_Y3(l, X3);

                X4 = Y2 - Y1 + X1;
                Y4 = calculate_Y4(l, X4);

                if(search_value(X3, Y3))
                    if(search_value(X4, Y4))
                        ++res;
            }

     res /= 2;

     FILE *g = fopen("patrate3.out", "w");

     fprintf(g, "%d\n", res);

     fclose(g);
}