Cod sursa(job #46271)

Utilizator sandyxpSanduleac Dan sandyxp Data 2 aprilie 2007 14:21:38
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

#define FIN "triang.in"
#define FOUT "triang.out"
#define PRECIZIE 0.001
#define egale(x,y) (fabs((x)-(y)) < PRECIZIE)
#define maimic(x,y) ((x)-(y) <= -PRECIZIE)
#define maimiceg(x,y) ((x)-(y) < PRECIZIE)
#define MAXN 1500

const double SIN60 = sqrt(3.0) / 2;

struct punct { double x, y; } ;
int n;
punct A[MAXN];

bool comp(const punct &a, const punct &b) {
    // return a.x < b.x || egale(a.x, b.x) && a.y < b.y;
    return maimic(a.x, b.x) || egale(a.x, b.x) && maimic(a.y, b.y);
}

bool operator==(const punct &a, const punct &b) {
    return egale(a.x, b.x) && egale(a.y, b.y);
}

bool operator<=(const punct &a, const punct &b) {
    return maimic(a.x, b.x) || egale(a.x, b.x) && maimiceg(a.y, b.y);
}

inline int search(int lo, int hi, punct x)
{
    int i, step, N = hi-lo;
    for (step=1; step < N; step <<= 1) ;
    for (i = 0; step; step >>= 1)
        if (i+step < N && A[i+step+lo] <= x)
            i += step;
    return i + lo;
}

void rez() 
{
    int i, j, triang = 0;
    double x, y, m, h, patr, c;
    punct t1, t2;

    std::sort(A, A+n, comp);
    for (i=0; i<n; ++i) {
        for (j=i+1; j<n; ++j) {
            // 2 pozitii posibile
            x = A[i].x - A[j].x;
            y = A[i].y - A[j].y;
            h = sqrt(x*x + y*y) * SIN60; // "inaltimea" triunghiului
            
            // ecuatia dreptei initiale : a=y, b=-x, c= never mind
            // daca ceva din a,b e 0, atunci dreapta e la dist -c/a sau -c/b de origine:
            // - (A[j].y*A[i].x - A[i].y*A[j].x) / (a sau b)

            if (egale(y,0)) { // e orizontala, a=0
                // 1,0,c  unde c=(A[i].x+A[j].x) / 2
                t1 = (punct) { (A[i].x + A[j].x)/2, A[i].y - h };
                t2 = (punct) { (A[i].x + A[j].x)/2, A[i].y + h };
            } else if (egale(x,0)) { // e verticala, b=0
                // 0,1,c  unde c=(A[i].y+A[j].y) / 2
                t1 = (punct) { A[i].x - h, (A[i].y + A[j].y)/2 };
                t2 = (punct) { A[i].x + h, (A[i].y + A[j].y)/2 };
            } else {
                // -m, 1, c
                m = (x) / (y); // panta mediatoarei, b/a al dreptei [ij]
                // c = m*(A[i].x+A[j].x)/2 - (A[i].y + A[j].y)/2;  /* c-ul mediatoarei, care are a=-m,b=1 */

                // x=x1-x2, x1 = x mijloc segment i,j , x2 = x punct3 (ala pe care-l cautam)
                // y=y2-y1, y1 = y mijloc segment i,j , y2 = y punct3
                // *** x^2 + y^2 = h^2 ( din formula distantei de la (1)=mijloc mediat la (2)=punct3 )
                // *** ax = by ( din diferenta formulelor dreptei (mediatoarei) cu punctele (1) si (2) )

                // Solutie : 
                // (+,-)  x = bh / sqrt(a^2 + b^2) ;   y = ah / sqrt(a^2 + b^2)
                patr = sqrt(m*m+1); // sqrt(a^2 + b^2)

                t1 = (punct) { (A[i].x + A[j].x)/2 - h/patr,  - m*h/patr + (A[i].y + A[j].y)/2 }; 
                t2 = (punct) { - (A[i].x + A[j].x)/2 + h/patr,  m*h/patr - (A[i].y + A[j].y)/2 }; 
            }
            // caut t1, t2 binar in [j+1, n)
            if (A[search(j+1, n, t1)] == t1 || A[search(j+1, n, t2)] == t2) 
                ++triang;
        }
    }
    printf("%d\n", triang);
}

void citire() 
{
    int i;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d", &n);
    for (i=0; i<n; ++i) 
        scanf("%lf %lf", &A[i].x, &A[i].y);
}

int main()
{
    citire();
    rez();
    return 0;
}